分布恒等与接近性测试

形式陈述

两个不同输入协议

Identity testing 给定显式已知分布 $q\in\Delta_n$ 和未知SAMP oracle $p$ ，要区分

p=q \quad\text{与}\quad d_{TV}(p,q)\ge\varepsilon.

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

Total variation在有限域上为

d_{TV}(p,q)=\frac12\sum_{i=1}^n|p_i-q_i|.

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

Identity 的最优量级

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

\Theta\!\left(\frac{\sqrt n}{\varepsilon^2}\right).

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

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

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

Closeness 的最优量级

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

\Theta\!\left( \max\left\{ \frac{n^{2/3}}{\varepsilon^{4/3}}, \frac{\sqrt n}{\varepsilon^2} \right\} \right)

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

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

直觉

恒等测试有一份可以直接查询概率值的参照，因此样本只需揭示未知分布偏离参照的总体信号。接近性测试的两边都带采样噪声；算法既要判断 observed difference 是否真实，又不能逐个学出大域上的轻元素，所以额外出现 $n^{2/3}/\varepsilon^{4/3}$ 这一困难区间。

最优统计量的共同思路是聚合，而不是搜寻一个显眼坏坐标。TV 距离可能由大量 $O(\varepsilon/n)$ 的小偏差共同组成，单项都淹没在抽样波动里；去偏的平方差或碰撞统计把这些微弱变化累积成可检测信号，同时控制 null 情形下的方差。

例子与边界

一个可计算的 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) =\frac12\left(\frac14+3\cdot\frac1{12}\right) =\frac14.

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

成功率与样本分配

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

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

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

推论与应用

这两项基准任务把分布测试中的三种信息来源区分开来：显式概率表、普通样本和更强的条件或求值 oracle。更换其中任何一项都可能改变最优量级，因而调用结论时必须同时带上域大小、距离阈值、成功率和每个 oracle 的样本预算。

它们也是判断“测试是否比学习便宜”的典型例子。Identity 只需 $\Theta(\sqrt n/\varepsilon^2)$ 个样本就能否定最坏参考分布，而以 TV 误差学习一般 $n$ 点分布需要线性依赖于 $n$ ；任务只要求一个 gap 判定 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.

形式陈述 ​

两个不同输入协议 ​

Identity 的最优量级 ​

Closeness 的最优量级 ​

一个可计算的 TV 实例 ​

成功率与样本分配 ​