性质测试模型

从隐藏错误理解查询下界 ​

考虑全零性质：只要命中一个 $1$ 就能发现错误，但在命中之前，算法无法知道隐藏位置在哪里。取 $k=\lceil \epsilon n\rceil$，比较全零输入与另一种输入：从 $n$ 个位置中均匀选择 $k$ 个位置放置 $1$。后者一定与全零性质相距至少 $\epsilon$。

对任何至多查询 $q$ 次、允许自适应的随机算法，固定其随机数后，观察它在全零输入上的查询位置。这是一条至多含 $q$ 个不同位置的路径。在碰到某个隐藏的 $1$ 之前，另一个输入给出的答案全是零，所以算法会沿着同一条路径执行。

每个固定位置被选入隐藏集合的概率是 $k/n$，并合界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。给出

将两次执行使用同一组随机数耦合：只要没有命中隐藏集合，两次输出就相同。因此两种输入分布的接受概率之差至多为 $qk/n$。一个双侧错误至多 $1/3$ 的测试器，却必须使两种接受概率至少相差 $1/3$，所以

由于 $k=\lceil \epsilon n\rceil$，这给出

与常数错误率的上界匹配。这个论证覆盖了自适应与双侧错误算法，而不只是说明某个朴素抽样器需要这么多样本。

补充示意图

一个完整测试器：字符串是否全为零 ​

取 $\mathcal{P}=\{0^n\}$。此时距离就是输入中 $1$ 的比例。算法独立均匀抽取 $q$ 个坐标，只要发现一个 $1$ 就拒绝，否则接受。

若 $x=0^n$，算法始终接受；若 $x$ 中至少有 $\epsilon n$ 个 $1$，一次查询没发现它们的概率至多为 $1-\epsilon$，所以

因此对目标错误率 $0<\delta \le 1/3$，取

即可。若这个预算超过 $n$，直接检查全部坐标更合适，得到 $O(min\{n,{\epsilon }^{-1}\log \left(1/\delta \right)\})$ 次查询。抽样时已经读过的坐标可以缓存，不必重复付出查询成本。

算法只要求查到一个见证，并不需要估计 $1$ 的精确比例。若目的是估计该比例到加性误差 $\epsilon$，通常的均值估计会出现 ${\epsilon }^{-2}$ 级样本量；那是不同任务，不能拿它替代这里的 ${\epsilon }^{-1}$ 分析。

这个测试器还是单侧错误的：合法输入绝不会被拒绝。它的复杂度对固定 $\epsilon ,\delta$ 不依赖 $n$，但这并不意味着每种性质都具有与输入长度无关的测试器。

普通性质测试只对距离为零和距离至少 ε 两侧作保证；中间区域的输出可以任意。

远离性质，不等于随机局部检查容易找到错误 ​

全零例子很简单，是因为每个为 $1$ 的坐标单独就是违例，距离直接等于这种局部见证的密度。一般性质没有这么直接的对应。

例如检测二进制序列是否单调不减。取偶数 $n$，输入为

它到所有单调不减序列的最小距离为 $1/2$：无论把零一分界放在哪里，至少要改掉一半坐标。但在全部相邻位置对中，只有正中间那一对呈现 $1,0$ 的逆序。因此随机抽查一个相邻对，发现违例的概率只有 $1/(n-1)$。

这并不证明单调性不可高效测试。它说明，“输入远离性质”与“某种指定的局部检查经常失败”之间需要一个结构定理。一个差的查询分布可能很难发现错误，而更合适的跨尺度或非相邻比较能利用更多结构。具体方法见 单调性测试理路单调性测试Monotonicity testing · Testing monotone functions在带偏序的有限定义域上，通过函数值 oracle 区分单调函数与必须修改 ε 比例点值才能单调的函数。。

另一个典型例子是 BLR 线性测试理路BLR 线性测试BLR linearity test · Blum-Luby-Rubinfeld linearity test以三个函数值检查 f(x)+f(y)=f(x+y)，并用 Fourier 一致性证明高通过率函数接近某个线性函数。：对 $f:{\mathbb{F}}_2^d\to {\mathbb{F}}_2$，随机选 $x,y$，检查

测试器只有三次查询，真正的数学工作却是证明：如果绝大多数这样的局部方程成立，$f$ 必须接近某个全局线性函数。性质测试的重要成果常常是简洁算法与非平凡结构分析的结合，而不是复杂的执行流程。[1]

容忍测试：接受区域也向外扩展 ​

普通测试区分距离为零与距离至少为 $\epsilon$。容忍性质测试理路容忍性质测试Tolerant property testing · Tolerant tester用两个有间隔的距离阈值区分接近性质与远离性质的对象；下阈值允许为零，并将间隔宽度纳入查询复杂度。则给定 $0\le {\epsilon }_1<{\epsilon }_2$，要求接受距离至多 ${\epsilon }_1$ 的输入，拒绝距离至少 ${\epsilon }_2$ 的输入。

当 ${\epsilon }_1=0$、${\epsilon }_2=\epsilon$ 时，就得到本条目的普通测试模型。因此在允许零端点的定义下，普通性质测试确实是容忍测试的特例。若某处将“容忍”一词专用于 ${\epsilon }_1>0$，应说明该术语限制，而不应因此混淆两种任务的关系。

正的容忍半径改变了算法需要做到的事：看到一个违例，已经不足以拒绝，因为合法的接受区域允许少量错误。比如全零性质的容忍测试若区分密度至多 $1/10$ 与至少 $1/5$，看到一个 $1$ 对两侧都可能发生，不能作为拒绝证据。可改为估计抽样中 $1$ 的比例，并在中点 $3/20$ 作判定；估计误差小于 $1/20$ 时两侧都正确。一般间隔 $\mathrm{\Delta }={\epsilon }_2-{\epsilon }_1$ 下，独立样本均值给出 $O({\mathrm{\Delta }}^{-2}\log \left(1/\delta \right))$ 的查询上界（也可读完输入）。这只是通用上界，并非所有参数区间的紧界，却清楚说明了为何接受少量错误后，寻找单个见证必须改成密度判断。

怎样判断一个性质适合哪种测试路线 ​

可以从三个相互衔接的问题入手。第一，离性质很远意味着哪些全局结构必须失败？第二，这些失败会在什么查询分布下留下足够密集的局部见证？第三，少量查询看不到这些差异时，能否构造两类输入分布证明下界？

全零测试把三问都化成“隐藏的 $1$ 是否被命中”；单调性例子说明局部见证的选择不能想当然；BLR 则展示局部代数关系如何约束全局函数。这些机制比“随机看几个位置”更准确地刻画性质测试。

继续学习时，可先读 查询复杂度模型理路查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。明确访问成本，再读 确定性与随机查询复杂度理路确定性与随机查询复杂度Deterministic query complexity · Randomized query complexity以决策树和量词定义确定性、允许错误与零错误查询成本，用 OR、奇偶与带间隔多数解释随机化的作用。理解自适应、错误率与下界。性质测试是在这些模型中加入距离承诺的近似判定框架。