分布测试模型

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

设离散域为 $[n]$，未知对象是概率向量

$$p=(p_1,\dots ,p_n)\in {\mathrm{\Delta }}_n,p_i\ge 0,\sum _i{p}_i=1.$$

性质 $\mathcal{P}\subseteq {\mathrm{\Delta }}_n$ 是一组分布，例如均匀分布、单调分布或支持大小受限的分布。测试器要区分 $p\in \mathcal{P}$ 与 $p$ 到性质至少 $\epsilon$，通常距离取 total variation。

与普通性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。的坐标 oracle 不同，sample 模型不能指定“读取 $p_i$”；它只能接收由 $p$ 随机生成的观测。对象随机性与测试器内部随机币是两层概率来源，保证必须对联合实验或条件顺序写清。

IID sample access ​

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

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

样本复杂度是达到给定错误所需的最小 $m$。经验测度公理库独立同分布样本与经验测度IID sample · Empirical measure用乘积分布描述独立重复观测，并把有限样本写成可积分的经验分布。记录频数 $N_i=|\{t:X_t=i\}|$ 与 ${\hat{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 有意义。

子集质量的样本轨迹 ​

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

$$Z_t=\mathbf{1}[X_t\in A],\hat{p}(A)=\frac{1}{m}\sum _{t=1}^m{Z}_t.$$

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

$$\text{Pr}[|\hat{p}(A)-p(A)|>\epsilon ]\le 2e^{-2m{\epsilon }^2},$$

所以 $m=O({\epsilon }^{-2}\log \left(1/\delta \right))$ 足以达到加性误差 $\epsilon$、失败率 $\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 \epsilon$ 时以至少 $2/3$ 拒绝。中间 gap 仍无约束；样本噪声不会把基础模型自动变成 tolerant testing。

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

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

失败边界 ​

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

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

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

参考资料

• 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.
• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapter 11.
• Dana Ron, “Property Testing: A Learning Theory Perspective,” Foundations and Trends in Machine Learning 1(3), 2008, distribution-testing sections.