【理论学习】property testing——应用yao's principle的一个示例

发表于 更新于 分类于

property testing（性质检验）是一个专门的研究领域，中文互联网上最好的一篇介绍目前看来是CSDN的一篇博客，已注在本文最后。本文仅用一个property testing作为例子来应用yao’s principle，例子来自NUS的一篇lecture note——Yao’s Principle: Three Examples

问题

以一个长度为的数组作为输入，现在需要：

在该数组是的情况下，以至少2/3的概率接受(accept)，

或者

在该数组是的情况下，以至少2/3的概率拒绝(reject)。

all zero即整个数组全都是0，

ε-far from all zero即数组里有至少个1，ε是常数且。

我们的问题并不是设计出这个算法，而是需要证明：

任何满足上述条件的算法都需要查询数组中个位置的值。

解决

请先回顾一下yao’s principle，然后再看下面的证明。

我们需要构造一个“足够差”的输入分布。方便起见，我们假设，把整个数组分成个大小为的块。我们随机地选择一个块，然后将其设为全 ，其他块都设为，也即产生一个ε-far from all zero的数组。现在，以的概率将全0的数组作为输入，以的概率将刚刚构造的数组作为输入。

下面证明这个输入足够差。

假设算法查询了个位置（注意，这不是查询了1/3个数组，而是块的数量乘1/3），而且恰好探测到的全是0，那么一个确定性算法只有可能作出下面两种反应之一：

  1. 认为这是一个all zero数组并接受。什么情况下这个反应是错的呢？需要输入的事实上是ε-far from all zero的数组（概率为），并且恰好探测到的都是0（概率为）。那么错误概率就是，相应的，正确概率就是，刚刚满足要求；

  2. 认为这是一个ε-far from all zero数组并拒绝，那么答对概率是。不符合要求。

如此可见，任意确定性算法在仅查询了个位置的情况下都有至少的概率犯错，那么为了满足题设，我们需要的查询数量就至少要，即。

由yao’s principle，任意随机算法也都需要查询数组中个位置的值。

综上，任意算法都需要查询数组中个位置的值。

这蕴含着yao’s principle的一个特例：

property testing

再聊聊

关于原问题会有一个疑惑，那就是问题中的两个描述难道不能统一为“ε-near from zero”吗？
其实不能。
严格的描述是：
accept, when all zero, with probability at least 2/3
reject, when ε-far from all zero, with probability at least 2/3
也就是说，这里对算法遇到非all zero的ε-near的反应没有做任何要求，甚至可以是不可判定的，学过可计算理论的朋友应该很熟悉相关的理论和例子（比如问题可判断但其补不可判定等等）。

另外，为什么在证明时只讨论全0的情况呢？

因为含有1的情况很复杂啊！可能有1个1，有2个1……并且对于每种情形我们都要考虑不同确定性算法对其的反应，挑出表现最好的那个算法，那就要讨论很多很多东西，所以我们就只考虑全0的情况。

【学习笔记】Property Testing（性质检验）_囚生CY的博客-CSDN博客

Property testing - Wikipedia

Yao’s Principle: Three Examples