COMP5270 Week 11 总结：Learning and Testing Probability Distributions（题解 + 知识点）

Posted on Edited on In , Word count in article: 4.3k Reading time ≈ 16 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 11 - Learning and testing probability distributions, Week 11 - Tutorial 11 (Solutions), Lotto CSV data

Part 1: Tutorial 11 详细题解

Warm-up

Problem 1: Pearson-Neyman lemma 与 Alice-Bob game

题目: 解释 Pearson-Neyman lemma 如何推出 Alice-Bob game 的 interpretation。

题解:

游戏中 Alice 先抛公平硬币：

  • Heads：从 抽样 ；
  • Tails：从 抽样 。

Bob 看到 后猜硬币结果。

设 Bob 的策略是一个 distinguisher：

Bob 输的概率：

因为硬币公平：

这正是：

Pearson-Neyman lemma 给出：

所以：

等价地：

这说明 total variation distance 正好刻画了“单个样本能把 区分开多少”。

本题用到的知识点:

  1. Type I / Type II errors。
  2. Pearson-Neyman lemma。
  3. Total variation 的 indistinguishability interpretation。

Problem 2: 用 Hoeffding 证明 coin bias learning upper bound

题目: 直接用 Hoeffding 证明 Corollary 51.1 的 upper bound。

题解:

设 是独立 coin flips：

用 empirical estimator：

则：

Hoeffding inequality 对 bounded independent variables 给：

要让右边不超过 ，只需：

即：

所以：

本题用到的知识点:

  1. Empirical mean 是 Bernoulli bias 的无偏估计。
  2. Hoeffding 给 additive deviation。
  3. 解指数尾界得到 sample complexity。

Problem 3: 与 不满足 Data Processing Inequality

题目: 说明分布间的 和 距离不满足 Data Processing Inequality。

题解:

构造反例。令 为偶数，domain：

令 是 上均匀分布：

令 是前一半元素上的均匀分布：

计算：

对前 个点，差值是：

对后 个点，差值也是：

所以：

而：

现在定义 post-processing function：

令 是 后的分布。

则 在 上均匀：

而 全部质量在 1：

于是：

当 时：

所以 被 post-processing 增大。

同理：

因此 都不满足 DPI。

本题用到的知识点:

  1. Data Processing Inequality：同样 post-processing 不应增大距离。
  2. TV 满足 DPI，但一般 不满足。
  3. 合并 bins 可能放大 差异。

Problem 4: 证明 Scheffe's lemma

题目: 证明：

题解:

定义 Scheffe set：

对这个集合：

另一方面，因为：

正差值总和等于负差值绝对值总和：

因此：

所以：

接下来证明它是 supremum。对任意 ：

  • 在 外，，加入这些点不会增加 ；
  • 在 内，，漏掉这些点只会减少差值。

所以最优集合正是 ：

最终：

本题用到的知识点:

  1. Scheffe set 。
  2. 概率分布总质量相同，正负差值平衡。
  3. TV 是 half 。

Problem Solving

Problem 5: Distribution learning 的两个 suboptimal sample complexities

题目: 证明两个学习分布的 suboptimal sample complexity，并说明如何去掉 假设。

题解:

设 domain 大小为 ，empirical estimator：

对固定 ，这是 Bernoulli mean estimator。

方法 1: 每个坐标 additive 精度

若对所有 都有：

则：

对每个坐标用 Hoeffding，并把失败概率设为 ：

需要：

这是第一种 suboptimal bound。

方法 2: 每个坐标 multiplicative 精度

如果能保证：

对所有 成立，则：

但 multiplicative estimation 对非常小的 很难。若假设：

用 Chernoff 可得：

课程选：

得到：

去掉 假设

把 与 uniform distribution 混合：

取：

则：

且对每个 ：

现在可以用 multiplicative bound 学习 到 TV 距离 ，再由 triangle inequality：

本题用到的知识点:

  1. Empirical distribution。
  2. TV = half 。
  3. 坐标级 Hoeffding + union bound。
  4. Multiplicative Chernoff 需要 lower bound on probabilities。
  5. Mixing with uniform 增加最小质量。

Problem 6: 只看独立 pairs 的 uniformity tester

题目: 不看所有 对样本，而是把 个样本分成 个 independent pairs，用它们估计 。分析 sample complexity。

题解:

假设 为偶数。把样本分成：

定义：

则 是 i.i.d. Bernoulli，且：

Uniform distribution 下：

若 距 uniform 在 TV 上 -far，则由讲义中的 proxy 可得：

所以要区分两个 Bernoulli means：

gap 是：

但 base mean 是 。用 coin testing 的 multiplicative form，需要 pair 数：

因此样本数：

这比讲义中碰撞 tester 用所有 pairs 的：

差很多。

原因是：只分成 对浪费了样本之间所有可能的 pair 信息；完整 collision tester 使用 个 pairs。

本题用到的知识点:

  1. Collision probability 。
  2. Uniformity testing 可转成估计 collision probability。
  3. 只用 disjoint pairs 会损失二次方信息。

Problem 7: Lotto 数据上的 TV、empirical estimator 与 uniformity testing

题目: 编程实现 TV distance、empirical estimator、uniformity tester，并在 Canada 6/49 lotto 数据上测试 bonus number 是否 uniform。

题解:

我用本地课程提供的 CSV：

chapter-11/Week 11 - Tutorial 11_ Data from the Canadian 6_49 Lotto.csv

共有：

条样本，bonus number domain 是：

a) Total variation function

对两个数组形式的分布 ：

b) Empirical estimator

对样本 multiset，统计每个值出现次数 ：

c) Collision uniformity tester

Algorithm 23 的 statistic：

等价于用 counts 写：

threshold：

若 ，输出 non-uniform；否则输出 uniform。

d-g) 本地数据结果

Bonus number 的 empirical TV distance to uniform：

collision statistic：

uniform baseline：

对题目给出的 ：

tester result
0.05 0.0205102 uniform
0.10 0.0208163 uniform
0.20 0.0220408 uniform
0.30 0.0240816 uniform
0.40 0.0269388 uniform
0.50 0.0306122 uniform

Bonus number 最常见的一些值：

number count
5 94
21 87
9 86
25 86
11 86

最少的一些值：

number count
15 53
6 54
2 56
29 60

结论：在这个简单 collision tester 下，bonus number 没有被判为 non-uniform。

补充：NUMBER DRAWN 1 的经验分布并不 uniform，TV 约：

这是合理的，因为 lotto 的第一个号码通常是排序后的最小号码，不应服从 上的 uniform distribution。

本题用到的知识点:

  1. Empirical distribution。
  2. TV distance。
  3. Collision statistic 可用 counts 快速计算。
  4. 数据字段含义很重要：排序后第一个号码不应按 uniform 检验。

Advanced

Problem 8: Laplace estimator

题目: Laplace estimator 定义为：

其中 是第 个 domain element 出现次数。证明它是分布，并用 divergence 推出 sample complexity。

题解:

a) 是 probability distribution

显然 。并且：

b) TV 与 divergence

定义：

由 Cauchy-Schwarz：

写成：

所以：

即：

c) 证明期望 bound

先化简：

令 ：

所以：

其中：

课程 solution 通过二项式系数计算得到：

代入：

d) 推出 learning sample complexity

由：

取期望：

再用 Markov：

要让失败概率 ，足够：

本题用到的知识点:

  1. Laplace smoothing。
  2. divergence。
  3. Cauchy-Schwarz 把 TV 关联到 。
  4. Markov 从 expected divergence 得 high-probability bound。

Part 2: Week 11 讲义知识点

0. 基础版导读：learning 和 testing distributions 的区别

Week 11 的主题是 Learning and Testing Probability Distributions。这一周的输入不再是一个显式数组或图，而是一个未知分布 。算法只能通过 samples 访问它：

核心问题有两类：

  1. Learning：估计整个分布 。
  2. Testing：只判断 是否满足某个性质，例如是不是 uniform。

这两类问题的 sample complexity 差别很大。学习通常需要更多样本，因为你要知道每个坐标大概是多少；检验只要判断“像不像”，有时可以用少得多的样本。

distribution 是什么?

在有限 domain 上，一个分布是：

满足：

样本 的意思是：

如果抽了 次，记 是看到元素 的次数。最自然的 empirical estimator 是：

Total variation distance 为什么最重要?

讲义用 total variation distance 衡量两个分布差多远：

它的直觉是： 和 在事件概率上最大能差多少。等价写法是：

这个等价形式就是 Scheffe's lemma。它很有用，因为 testing 本质上就是找一个事件 ，使得两个分布在这个事件上的概率差很大。

learning distribution 要多少样本?

要学习任意 维分布到 TV error ，标准 sample complexity 是：

为什么和 成正比? 因为有 个坐标，每个坐标都可能有误差。经验分布 的每个坐标都有随机波动，累加成 误差后需要足够多样本才能控制。

初学时可以记住：

learning 要恢复整个分布，所以每个 bucket 都要有足够信息。

testing uniformity 为什么样本更少?

Uniformity testing 只问：

  • : ，其中 。
  • : 。

不需要估计每个 ，只要判断是否明显偏离 uniform。经典 collision tester 的样本复杂度可以达到：

这比 learning 的 少很多。

collision idea 怎么理解?

如果从 uniform distribution on 抽样，两次独立样本相等的概率是：

对一般分布 ，两次样本相等的概率是：

如果 离 uniform 很远，通常会更“集中”，使得 变大。因此可以通过数 collisions 来检测非均匀性。

所以 uniformity tester 的基本流程是：

  1. 抽 个 samples。
  2. 统计有多少 pair 满足 。
  3. 和 uniform 情况下的期望 collision 数比较。

Pearson-Neyman lemma 的作用

Pearson-Neyman lemma 给出 TV distance 的 operational meaning：如果 Alice 从 或 中选一个分布生成样本，Bob 要猜是哪一个，那么最佳区分优势由 TV distance 控制。

直觉是：

TV distance 越大，两个分布越容易被区分；TV distance 越小，任何 tester 都难以区分。

这也是为什么 distribution testing 用 TV distance 作为自然距离。

Data Processing Inequality 是什么?

如果对样本做某个随机或确定性映射 ，得到 pushforward distributions 和 ，那么 TV distance 不会增加：

直觉是：处理数据只会丢信息，不会凭空制造更多可区分性。

注意 tutorial 里也强调：不是所有距离都有这个性质。例如 和 就不满足同样的 data processing inequality。

Hoeffding 在 coin bias learning 中怎么用?

如果 domain 只有两个结果，比如 coin 是 heads/tails，那么学习分布等价于估计 bias 。

令：

Hoeffding 给出：

所以要让失败概率小于 ，只要：

多维分布中会对每个坐标使用 concentration，再用 union bound 或其他方法控制总误差。

做题时怎么下手?

  • 问 learning：通常要估计整个 ，目标是 。
  • 问 testing：写清 completeness 和 soundness。
  • 问 TV：优先使用 或 Scheffe's lemma。
  • 问 uniformity：考虑 collision probability 。
  • 问 sample complexity：区分是 还是 。
  • 问 data processing：说明映射会合并事件、不会增加可区分信息。

1. 分布学习/检验的 setting

现在输入不是固定对象，而是未知分布 。算法只能通过 i.i.d. samples 访问它：

主要复杂度是 sample complexity：

其中：

  • 是 domain size；
  • 是距离/精度参数；
  • 是失败概率。

2. Total variation distance

定义：

Scheffe lemma：

范围：

3. Data Processing Inequality

若对 和 应用同一个随机/确定函数 ，得到分布 ，则：

也就是 post-processing 不会增加 TV distance。

4. Pearson-Neyman lemma

任何基于单样本区分 和 的 test，其 Type I + Type II errors 满足：

最优成功概率是：

5. Coin bias learning/testing

学习 coin bias 到 additive ，失败概率 ：

测试 fair coin vs 也需要同阶样本。

但若测试 very biased regime：

则：

6. Learning arbitrary distribution

目标：

最优 sample complexity：

算法就是 empirical distribution。

证明可以用：

  • 对所有 subsets 做 Hoeffding + union bound；
  • 或用 proxy 证明 constant probability。

7. Identity testing 与 uniformity testing

Identity testing：给定已知 ，区分：

和：

Uniformity testing 是特殊情形：

讲义指出 identity testing 可 reduction 到 uniformity testing，sample complexity 只差常数因子。

8. Uniformity testing 的 collision idea

Uniform distribution 的 collision probability：

任意 ：

并且：

若：

则由 Cauchy-Schwarz：

所以可通过统计 sample collisions 测试 uniformity。

9. Collision tester

统计：

若 显著大于 ，说明不均匀。

课程给出 suboptimal proof：

更精细分析可得：

这是 constant success probability 下 optimal。

高概率 optimal bound：

10. Learning vs testing

任务 Sample complexity
Learn arbitrary in TV
Test uniformity
Robust testing with gap 可更难，接近 regime

Testing 只输出一 bit，因此可能比 learning 省很多样本。

本周核心记忆

主题 关键结论
TV distance
DPI post-processing 不增加 TV
PN lemma 单样本区分优势是
Coin learning
Distribution learning
Uniformity testing constant success
Collision probability
Empirical estimator learning 的基本算法
Laplace estimator smoothing 后也有