分布恒等与接近性测试

形式陈述 ​

两个不同输入协议 ​

固定有限域 $[n]$ 与 $n\ge 2$，距离阈值取 $0<\epsilon \le 1$。Identity testing 给定显式已知分布 $q\in {\mathrm{\Delta }}_n$ 和未知SAMP oracle理路分布测试模型Distribution testing model · Distribution property testing区分分布访问接口，并用成对随机扰动、混合似然比二阶矩和四点算例完整证明均匀性测试的样本下界。 $p$，要区分

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

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

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

Identity 的最优量级 ​

以下最优量级统一取 $0<\epsilon \le 1/4$、成功率 $2/3$ 与最坏样本预算。在标准 IID sample access 下，最坏已知参考分布的 identity testing 样本复杂度为

上界可用按参考质量适当分组、截断或重加权的 Pearson／${\chi }^2$ 型统计量；不能把任意参考分布直接交给一个未经方差分析的平方和。若 $q_i=0$ 却抽到元素 $i$，可直接拒绝。对其余正参考质量，Cauchy–Schwarz 不等式理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。说明

当 $p$ 也支持在这些坐标上时，右端就是 $4d_{\mathrm{TV}}(p,q{)}^2$。这解释聚合平方偏差的信号来源；达到最优界还须控制统计量的方差。[1]

分析中常取 $\lambda >0$，先独立抽取总样本数 $N\sim \mathrm{Pois}(\lambda )$，再从 $p$ 抽 $N$ 次。此时各坐标计数精确独立，并满足 $N_i\sim \mathrm{Pois}(\lambda p_i)$。对任意非负整数 $k_i$、$K=\sum _i{k}_i$，由Poisson 分布理路Poisson 分布Poisson distribution · 泊松分布以强度参数描述固定窗口内稀有事件计数的离散分布。与条件计数概率直接得到

其中零强度坐标按恒为零的计数解释。若至少两个坐标具有正质量，固定正整数总样本数时，计数和受约束，这些坐标计数便不独立。Poisson 化也不自动给硬预算：可先把错误以常数次重复降到 $1/6$，将放大后总样本数的期望记为 $\mathrm{\Lambda }=O(\lambda )$，再在总数超过 $\lceil 12\mathrm{\Lambda }\rceil$ 时停止并任意作答。Markov 不等式理路Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。将额外失败界为 $1/12$，总错误至多 $1/4$，而样本数已有 $O(\lambda )$ 硬上限。

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

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

Closeness 的最优量级 ​

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

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

Closeness 不能通过先用少量样本“学出 $q$”再直接调用已知参考的恒等测试，就自动达到最优量级。大域上的经验参考会遗漏大量轻元素；即便得到接近 $q$ 的 $\hat{q}$，$p=q$ 也不意味着 $p=\hat{q}$，未满足恒等测试的 exact-yes 前提。Closeness 的 $n^{2/3}$ 项正反映两边都未知时的额外困难。