单调性测试

偏序域上的性质 ​

设 $(P,⪯)$ 是有限偏序集公理库偏序Partial order · Partially ordered set满足自反、反对称和传递性的关系。，值域 $(R,\le )$ 也带序。函数 $f:P\to R$ 单调，当且仅当

$$x⪯y⟹f(x)\le f(y)$$

对所有可比点成立。Tester 通过 value oracle 查询 $f(x)$，本地知道偏序关系和域大小。

距离通常按需要修改的函数表位置比例定义：

$$\mathrm{dist}(f,\mathrm{MON})=\frac{1}{|P|}\underset{g\in \mathrm{MON}}{min}|\{x\in P:f(x)\ne g(x)\}|.$$

测试器要接受所有单调函数，拒绝距离至少 $\epsilon$ 的函数。它不负责输出最近单调修复，也不按违反关系对的比例直接定义 far。

Boolean cube ​

最常见的域是 $P=\{0,1{\}}^n$，采用逐坐标偏序：$x⪯y$ 当且仅当每个 $i$ 都有 $x_i\le y_i$。对 Boolean-valued $f$，单调性禁止从较低点的 $1$ 走到较高点的 $0$。

Hasse 图的有向边连接只差一个从 $0$ 变 $1$ 的坐标。若某条边 $(x,x\oplus e_i)$ 满足

$$f(x)=1,f(x\oplus e_i)=0,$$

它是一个局部 violation，足以单侧拒绝。若所有 Hasse 边都不违反，则沿任意上升路径反复应用局部不减，函数对全部可比点单调。

Edge tester ​

一次 edge test 均匀选择 cube 中一条有向边，查询两端并在出现 $1\to 0$ 时拒绝。单调函数从不被拒绝，查询数为 $2$。

若 $f$ 是 $\epsilon$-far，可以从违反边端点构造必须修改的点集；反过来，若违反边过少，修改覆盖这些局部冲突的点并作单调延拓，会得到与 $f$ 接近的单调函数。标准计数给出随机边违反概率至少量级

$$\mathrm{\Omega }(\epsilon /n).$$

独立重复 $O(n/\epsilon )$ 次便得到常数 soundness。这个上界展示一个完整合法 tester，但不是 Boolean cube monotonicity 的所有最优结果；更精细算法会抽取长路径或使用更全局的比较。

一条真实违反轨迹 ​

在 $\{0,1{\}}^3$ 上，令 $f(010)=1$、$f(011)=0$。因为

$$010⪯011,$$

查询这条第三坐标边会立即给出 violation。无论其他六个点怎样赋值，当前 $f$ 都不可能单调，至少要修改这两个端点之一或重新定义其中一个值。

但只存在一个违反边不表示函数距单调性为常数；在 $2^n$ 个表位置中，它可能只需一次修改。性质测试的 soundness 需要从 $\epsilon$-far 推出 许多可命中证据或足够大的结构，不能把“发现一个反例”反向读成“远离”。

Violation graph 与距离 ​

定义 violation graph：顶点为 $P$，若 $x⪯y$ 但 $f(x)>f(y)$，就在两点间连边。任何修改集必须击中每条 violation，否则未修改的两个端点仍违反；因此修改集是该图的 vertex cover。

对 Boolean-valued 函数，删除一个 vertex cover 后，剩余标记间不存在可比的 $1\to 0$，可把未标点补成单调函数。于是最小 vertex cover 大小刻画 Hamming 修复距离。这个结构把“far”转换为许多互不相容的违反对，常用于 tester 分析。

只用 Hasse 边建立的图可能丢掉远距离可比对；虽然无局部违反等价于单调，但最小 cover 与完整 violation graph 的参数不必逐项相同。下界或精确距离论证要声明使用哪一张图。

模型边界 ​

Total order、Boolean cube、hypergrid 与任意 poset 的可比对密度不同。均匀抽点对在 cube 中几乎总不可比，不能把线性序上的 pair tester 直接搬来。

值域若为实数，violation 仍按顺序判断，但“修改一个值”的编辑与 $L_1/L_2$ 数值误差不同。测试 Boolean monotonicity 的查询界不自动适用于回归函数的数值距离。

域分布也可能非均匀。若距离按未知分布质量而不是均匀表位置计，采样和 far 定义都会改变；标准 uniform cube tester不能只换一个期望符号便保持 soundness。

参考资料

• Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky, “Testing Monotonicity,” Combinatorica 20, 2000, pp. 301–337.
• Deeparnab Chakrabarty and C. Seshadhri, “Optimal Bounds for Monotonicity and Lipschitz Testing over Hypercubes and Hypergrids,” STOC, 2013, pp. 419–428.
• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapter 4.