分布恒等与接近性测试

两个不同输入协议 ​

Identity testing 给定显式已知分布 $q\in {\mathrm{\Delta }}_n$ 和未知 SAMP oracle $p$，要区分

$$p=q\text{与}{d}_{TV}(p,q)\ge \epsilon .$$

Closeness testing 则同时获得两个未知 oracle $p,q$，要区分 $p=q$ 与 $d_{TV}(p,q)\ge \epsilon$。第二个问题不能免费读取参考概率，需要从两边都抽样估计差异，因此通常更难。

Total variation公理库总变差距离Total variation distance · TV distance两个概率分布对最优可测事件所赋概率之差的最大值。在有限域上为

$$d_{TV}(p,q)=\frac{1}{2}\sum _{i=1}^n|p_i-q_i|.$$

两项任务都采用 exact yes 与 far no 的 gap，不要求在 $0<d_{TV}<\epsilon$ 时作固定判断。若 yes 侧允许正距离，那是 tolerant 版本，样本复杂度会改变。

Identity 的最优量级 ​

在标准 IID sample access、成功率 $2/3$ 下，最坏已知参考分布的 identity testing 样本复杂度为

$$\mathrm{\Theta }\left(\frac{\sqrt{n}}{{\epsilon }^2}\right).$$

上界常用 Pearson/χ² 型统计量。Poissonize 样本数后，各坐标计数近似独立；对观测频数 $N_i$ 做去偏平方偏差聚合，使 $p=q$ 时期望接近 $0$，而 TV 至少 $\epsilon$ 时由 Cauchy–Schwarz 获得可检测的 ${\ell }_2$ 信号。

直接估计每个 $p_i$ 到加性 $O(\epsilon /n)$ 会需要远多于 $\sqrt{n}$ 样本。最优 tester 聚合许多微小偏差，只解决是否相等，不重建整个概率向量。

下界构造一族对均匀分布作随机正负微扰的 alternatives。样本太少时，碰撞与计数分布在 null/alternative 下接近，任何统计量都无法稳定区分；这与“某个坐标差很多”的容易实例不同。

Closeness 的最优量级 ​

两份未知分布的 closeness testing 最优样本数为

$$\mathrm{\Theta }(max\{\frac{n^{2/3}}{{\epsilon }^{4/3}},\frac{\sqrt{n}}{{\epsilon }^2}\})$$

从每个 oracle 各取该量级样本。统计量要同时消除两边采样噪声，并处理重元素与轻元素：重元素可较准确估计，轻元素数量多、单项稀疏，需要碰撞型聚合。

Identity 不能通过先用少量样本“学出 $q$”后直接套已知参考算法达到相同量级；一个经验参考在大域上会遗漏大量轻元素。Closeness 的 $n^{2/3}$ 项正反映两边都未知时的额外困难。

一个可计算的 TV 实例 ​

令已知参考为四点均匀分布

$$q=(1/4,1/4,1/4,1/4),$$

未知分布为

$$p=(1/2,1/6,1/6,1/6).$$

第一坐标多出 $1/4$，其余三坐标各少 $1/12$，所以

$$d_{TV}(p,q)=\frac{1}{2}(\frac{1}{4}+3\cdot \frac{1}{12})=\frac{1}{4}.$$

样本序列若频繁出现元素 $1$ 会推动统计量拒绝，但某一小批样本也可能碰巧接近均匀。测试保证来自整个计数统计的尾界，不是“看见两次 1 就判不等”之类固定阈值。

成功率与样本分配 ​

把成功率从 $2/3$ 提高到 $1-\delta$，可独立重复常数成功 tester 并多数表决，通常乘 $O(\log \left(1/\delta \right))$ 样本。更精细算法可能直接调阈值，但失败率依赖仍要报告。

Closeness 若两边样本预算不同，应写成 $(m_p,m_q)$ 的 trade-off；“总样本 $m$”不能默认意味着每边各 $m$。Known-reference identity 不需要从 $q$ 抽样，读取显式 $q_i$ 的计算时间则是另一资源。

失败边界 ​

上述最优式针对最坏 $n$ 点分布和标准 SAMP。若 $q$ 有已知小支持、概率质量下界或特殊结构，instance-optimal identity complexity 可更低；conditional/evaluation oracle 也会改变量级。

TV far 不表示存在某个坐标差至少 $\epsilon$。差异可分散到全部 $n$ 个坐标，每项只有 $O(\epsilon /n)$，所以逐点阈值扫描不是 sample-efficient 算法。

最后，检验 $p=q$ 与估计 $d_{TV}(p,q)$ 到加性误差是不同任务。后者要在整个距离区间输出数值，不能从 gap tester 的一次接受 bit 直接恢复。

参考资料

• Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White, “Testing That Distributions Are Close,” FOCS, 2000, pp. 259–269.
• Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant, “Optimal Algorithms for Testing Closeness of Discrete Distributions,” SODA, 2014, pp. 1193–1203.
• Clément Canonne, “A Survey on Distribution Testing: Your Data Is Big. But Is It Blue?” Theory of Computing Graduate Surveys 9, 2020, pp. 1–100.