分布测试模型 | Codeboy's Blog

形式陈述

对象不是一条固定字符串

固定整数 $n\ge1$ ，设离散域为 $[n]$ ，未知对象是概率向量

p=(p_1,\ldots,p_n)\in\Delta_n, \qquad p_i\ge0,\quad\sum_i p_i=1.

性质是非空分布集合 $\mathcal P\subseteq\Delta_n$ ，例如均匀分布、单调分布或支持大小受限的分布。本文取总变差距离，并定义 $d_{\mathrm{TV}}(p,\mathcal P)=\inf_{q\in\mathcal P}d_{\mathrm{TV}}(p,q)$ 。给定 $0<\varepsilon\le1$ ，测试器区分 $p\in\mathcal P$ 与到性质的距离至少为 $\varepsilon$ ；不满足这两项前提的分布没有输出要求。性质不闭时，下确界不必达到，也可能有非成员的距离为零。

与普通性质测试的坐标 oracle 不同，sample 模型不能指定“读取 $p_i$ ”；它只能接收由 $p$ 随机生成的观测。对象随机性与测试器内部随机币是两层概率来源，保证必须对联合实验或条件顺序写清。

IID sample access

标准 SAMP oracle 每次返回独立样本 $X\sim p$ 。调用 $m$ 次得到一份IID 样本

X_1,\ldots,X_m\stackrel{\mathrm{iid}}\sim p.

样本复杂度是达到给定错误所需的最小 $m$ 。当 $m\ge1$ 时，经验测度记录频数 $N_i=|\{t:X_t=i\}|$ 与 $\widehat p_i=N_i/m$ ，但 tester 可以使用碰撞数、缺失质量等统计量，不必先完整估计 $p$ 。

样本结果由分布决定，算法不能要求下一次一定观察某个低概率元素。根据先前样本决定是否继续会产生随机样本量；此时要声明最坏、期望或高概率 sample bound。

其他查询接口

Evaluation oracle 接收 $i\in[n]$ 并返回 $p_i$ ，通常假设精确实数或指定精度；它比 SAMP 直接暴露坐标质量。若返回近似值，容差和 bit 精度必须计入模型。

Conditional oracle 接收集合 $S\subseteq[n]$ ，在 $p(S)>0$ 时返回条件分布 $p(\cdot\mid S)$ 的样本。它能把观测集中到原分布中罕见区域；若 $p(S)=0$ ，oracle 返回什么必须约定，不能让该响应偷偷泄露无限信息。

Pair-conditional、cumulative、dual access 等模型继续改变可见信息。相同性质在这些接口下可有指数不同的复杂度，因此“distribution testing 需要多少样本”只对具体 access model 有意义。

直觉

分布测试器不能直接读取完整概率向量；SAMP 只让它从未知质量中随机看到元素，EVAL 和 COND 则暴露不同强度的局部信息。访问模型决定罕见区域能否被主动观察，因此样本数或查询数必须与 oracle 类型、域大小和误差口径共同陈述。

例子与边界

子集质量的样本轨迹

固定已知集合 $A\subseteq[n]$ ，要估计 $p(A)$ 。从 SAMP 获得样本后记录

Z_t=\mathbf1[X_t\in A], \qquad \widehat p(A)=\frac1m\sum_{t=1}^mZ_t.

$Z_t$ 是均值 $p(A)$ 的 IID Bernoulli 变量。Hoeffding 界给出

\Pr[|\widehat p(A)-p(A)|>\varepsilon] \le2e^{-2m\varepsilon^2},

所以对 $0<\delta\le1/3$ ， $m=O(\varepsilon^{-2}\log(1/\delta))$ 足以达到加性误差 $\varepsilon$ 、失败率 $\delta$ 。这条轨迹只估计一个预先给定集合的质量，不代表以同样样本量逐坐标准确恢复全部 $n$ 个概率。

若改用 EVAL，可将 $p_i$ 对 $i\in A$ 求和，但需要 $|A|$ 次查询；COND 则可直接在 $A$ 内采样，却不立即告诉 $p(A)$ 的绝对大小。更强接口提供不同信息，不存在统一的“每次查询价值”。

完备性、可靠性与距离

一个 sample tester 在 $p\in\mathcal P$ 时以至少 $2/3$ 接受，在 $d_{TV}(p,\mathcal P)\ge\varepsilon$ 时以至少 $2/3$ 拒绝。中间 gap 仍无约束；样本噪声不会把基础模型自动变成 tolerant testing。

概率包括 $X_1,\ldots,X_m$ 的抽样和算法额外随机币。固定一份“典型样本集”再对所有 $p$ 声称正确，通常交换了量词；保证应对每个固定 $p$ 分别取样。

域大小 $n$ 、精度 $\varepsilon$ 、置信度 $\delta$ 和访问类型都要出现在复杂度中。把 $n$ 吸进常数，会掩盖 distribution testing 最主要的次线性现象。

推论与应用

一个完整下界：均匀性需要多少 IID 样本

固定 $n\ge2$ 、 $0<\varepsilon\le1/4$ ，参考为 $u=(1/n,\ldots,1/n)$ 。测试器只获得未知 $p$ 的SAMP访问：若 $p=u$ ，以至少 $2/3$ 接受；若 $d_{\mathrm{TV}}(p,u)\ge\varepsilon$ ，以至少 $2/3$ 拒绝。假设样本数有整数硬上限 $m$ ，允许内部随机性和提前停止。下面完整证明

\boxed{m\ge\frac{\sqrt{n\log(13/9)/54}}{\varepsilon^2} =\Omega\!\left(\frac{\sqrt n}{\varepsilon^2}\right).}

这里 $\log$ 是自然对数； $n$ 为偶数时可把常数54改成16。思想采用Paninski的成对扰动，以下统一使用TV距离、固定样本预算，重新计算奇数域与显式常数。[4] 这是下界，不把匹配上界或期望样本预算混入本次证明。

隐藏符号只抽一次

设 $k=\lfloor n/2\rfloor$ 、 $a=n\varepsilon/k$ 。由于 $n/k\le3$ ，有 $0<a\le3/4$ 。对每个符号向量 $\sigma\in\{-1,1\}^k$ ，定义

p_\sigma(2i-1)=\frac{1+a\sigma_i}{n},\qquad p_\sigma(2i)=\frac{1-a\sigma_i}{n}\quad(1\le i\le k).

若 $n$ 为奇数，剩余坐标取 $p_\sigma(n)=1/n$ 。每对总质量为 $2/n$ ，各坐标非负，故这确是分布；而

d_{\mathrm{TV}}(p_\sigma,u) =\frac12(2k)\frac an=\frac{ka}{n}=\varepsilon.

现在从所有符号向量中均匀选取一个 $\sigma$ ，然后整组 $m$ 个样本都从这个固定 $p_\sigma$ 独立抽取。比较样本空间 $[n]^m$ 上的两个分布：

U_m=u^{\otimes m},\qquad Q_m=2^{-k}\sum_{\sigma\in\{-1,1\}^k}p_\sigma^{\otimes m}.

$Q_m$ 是不同IID实验的混合；在隐藏 $\sigma$ 后，样本之间一般不再独立。它不是 $(\mathbb E_\sigma p_\sigma)^{\otimes m}$ 。后者恰等于 $U_m$ ，对应每次抽样都重新换一个未知分布，已经改变了测试任务。

正确测试器迫使两个样本分布相距至少三分之一

对给定样本串 $z$ ，记 $g(z)\in[0,1]$ 为测试器在自身随机币下的拒绝概率。最坏至多 $m$ 次采样的自适应停止算法，也可先预生成 $m$ 个样本，再只按需读取；未使用的样本被忽略。这不会改变其输出分布。

在 $U_m$ 下， $\mathbb E g\le1/3$ ；每个 $p_\sigma$ 都是合法远离实例，所以在混合 $Q_m$ 下， $\mathbb E g\ge2/3$ 。对任何取值在 $[0,1]$ 的函数，期望差不超过总变差距离：将正差部分求和便有

\mathbb E_{Q_m}g-\mathbb E_{U_m}g \le\sum_{z:Q_m(z)>U_m(z)}(Q_m(z)-U_m(z)) =d_{\mathrm{TV}}(Q_m,U_m).

因此任何满足规格的测试器都要求 $d_{\mathrm{TV}}(Q_m,U_m)\ge1/3$ 。接下来证明样本少时做不到；这个论证约束所有测试器，不只是某个碰撞统计量。

似然比的二阶矩

因为 $U_m$ 在有限样本空间处处为正，定义

L(z)=\frac{Q_m(z)}{U_m(z)},\qquad \chi^2(Q_m\Vert U_m)=\mathbb E_{U_m}(L-1)^2.

这里的 $\chi^2$ 是两个分布之间的散度，不是一个声称服从卡方分布的随机统计量。Cauchy–Schwarz 不等式给出

d_{\mathrm{TV}}(Q_m,U_m) =\frac12\mathbb E_{U_m}|L-1| \le\frac12\sqrt{\chi^2(Q_m\Vert U_m)}.

令 $\tau$ 为独立于 $\sigma$ 的另一个均匀符号向量。把混合似然比平方，展开有限和，再用 $U_m$ 下各样本独立，得到精确恒等式

\begin{aligned} 1+\chi^2(Q_m\Vert U_m) &=\mathbb E_{U_m}L^2\\ &=\mathbb E_{\sigma,\tau} \left(\sum_{x=1}^{n}\frac{p_\sigma(x)p_\tau(x)}{u(x)}\right)^m\\ &=\mathbb E_{\sigma,\tau} \left(1+\frac{2a^2}{n}\sum_{i=1}^{k}\sigma_i\tau_i\right)^m. \end{aligned}

最后一步逐对相加：一对坐标对内积的贡献是

\frac{(1+a\sigma_i)(1+a\tau_i)+(1-a\sigma_i)(1-a\tau_i)}{n} =\frac{2+2a^2\sigma_i\tau_i}{n}.

奇数域的最后坐标另贡献 $1/n$ ，恰好补齐常数项1。括号的最小值至少为 $1-a^2>0$ ，所以即使内积增量为负，也能使用 $(1+s)^m\le e^{ms}$ 。

从独立符号到指数界

乘积 $Z_i=\sigma_i\tau_i$ 是相互独立、等概率取 $\pm1$ 的符号。因此

\begin{aligned} 1+\chi^2(Q_m\Vert U_m) &\le\mathbb E\exp\!\left(\frac{2ma^2}{n}\sum_{i=1}^k Z_i\right)\\ &=\cosh\!\left(\frac{2ma^2}{n}\right)^k\\ &\le\exp\!\left(\frac{2km^2a^4}{n^2}\right). \end{aligned}

最后一个不等式也可直接证明： $\log\cosh z$ 为偶函数；对 $z\ge0$ ，其导数为 $\tanh z\le z$ ，从0积分得到 $\log\cosh z\le z^2/2$ 。代入 $a=n\varepsilon/k$ ，有

\frac{2ka^4}{n^2} =\frac{2(n/k)^3\varepsilon^4}{n} \le\frac{54\varepsilon^4}{n}.

偶数 $n$ 恰有 $n/k=2$ ，常数为16。由此

\frac13\le d_{\mathrm{TV}}(Q_m,U_m) \le\frac12\sqrt{\exp\!\left(\frac{54m^2\varepsilon^4}{n}\right)-1}.

移项得到 $\exp(54m^2\varepsilon^4/n)\ge13/9$ ，取对数即为开头的样本下界。所有式子对固定整数样本数成立，没有泊松化或隐含的样本数转换。

四点空间：一份样本完全看不见，两份开始显露

取 $n=4,\varepsilon=1/4$ ，则 $k=2,a=1/2$ 。四个备择分布为

\frac18(3,1,3,1),\quad \frac18(3,1,1,3),\quad \frac18(1,3,3,1),\quad \frac18(1,3,1,3).

每个与 $u$ 的TV都是 $1/4$ ，但四者平均恰为 $u$ ，因此 $Q_1=U_1$ 。对两个有序样本，混合质量矩阵为

Q_2=\frac1{64} \begin{pmatrix} 5&3&4&4\\ 3&5&4&4\\ 4&4&5&3\\ 4&4&3&5 \end{pmatrix},\qquad U_2=\frac1{64} \begin{pmatrix} 4&4&4&4\\ 4&4&4&4\\ 4&4&4&4\\ 4&4&4&4 \end{pmatrix}.

同一坐标的4格各增加 $1/64$ ，同一扰动对中的相反坐标4格各减少 $1/64$ ，跨对8格不变。因此

d_{\mathrm{TV}}(Q_2,U_2)=\frac1{16},\qquad \chi^2(Q_2\Vert U_2) =8\frac{(1/64)^2}{1/16}=\frac1{32}.

即使把全部两个样本都交给任意复杂的测试器，拒绝概率差也至多 $1/16$ ，不足以达到 $1/3$ 。只比较每个单独样本的均匀边缘，会漏掉这张联合表中的全部差异。

能迁移的结论与模型边界

均匀分布是显式参考分布的特例，故这一族已经给出恒等测试的最坏参考样本下界。它没有证明对每个固定参考都同样难，也没有给出匹配上界。

如果测试器获得精确EVAL，查询本构造中的坐标1便看到 $(1\pm a)/n\ne1/n$ ，因此该困难族不再隐藏。同样，只有期望样本数上界时，不能直接预生成固定的 $m$ 个样本来覆盖所有运行；须另作截断并支付错误预算。上述证明的条件是普通SAMP和最坏样本预算。

失败边界

经验分布与真实分布在大域上可能 total variation 很远：当 $m\ll n$ 时，经验测度只支持至多 $m$ 个元素。Tester 的目标是判定某项性质，不是先让 $\widehat p$ 在 TV 中一致逼近 $p$ 。

IID 假设也不能省略。时间序列、无放回样本或自适应污染会改变碰撞和浓缩分析；相同边缘分布不足以保证标准样本复杂度。

最后，生成样本的计算成本通常不计入测试器资源。若现实中每个样本获取代价不同，应另加采集成本，不能从信息论 sample bound 直接读运行费用。

参考资料

[1] 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.

[2] Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapter 11.

[3] Dana Ron, “Property Testing: A Learning Theory Perspective,” Foundations and Trends in Machine Learning 1(3), 2008, distribution-testing sections.

[4] Liam Paninski, “A coincidence-based test for uniformity given very sparsely-sampled discrete data”, IEEE Transactions on Information Theory54(10), 2008, pp.4750–4755：作者稿PDF第4–5页，LOWER BOUND、Theorem4及其证明。原稿以L1距离记阈值、以m记域大小、N记样本数；本文重新推导TV口径的固定预算下界，包含奇数域和显式常数，未把其渐近一致性或上界作为本页已证明结论。

形式陈述 ​

对象不是一条固定字符串 ​

IID sample access ​

其他查询接口 ​

子集质量的样本轨迹 ​

完备性、可靠性与距离 ​

一个完整下界：均匀性需要多少 IID 样本 ​

隐藏符号只抽一次 ​

正确测试器迫使两个样本分布相距至少三分之一 ​

似然比的二阶矩 ​

从独立符号到指数界 ​

四点空间：一份样本完全看不见，两份开始显露 ​

能迁移的结论与模型边界 ​

失败边界 ​

反向链接