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

Posted on 2026-06-01 Edited on 2026-06-14 In Course Notes , COMP5270 Word count in article: 6.4k Reading time ≈ 23 mins.

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

Part 1: Tutorial 11 详细题解

各题难度/要求说明：

Problem 1：概念理解，重要，必做。
Problems 2–4：技术性稍强，可跳过，但 Problem 2 是好练习，Problem 4 的思路重要。
Problem 5：好练习，较长，时间不够时可跳过后自行完成。
Problem 6：说明直观做法为何不够好，可选。
Problem 7：重要，将课堂算法应用于实际（Lotto 数据集）。
Problem 8（进阶）：加深理解，值得在完成其他题后尝试。

Problem 1（Warm-up）：Pearson–Neyman 引理 → Alice-Bob 游戏

题目：解释 Lemma 50.1（Pearson–Neyman）如何蕴含 Alice-Bob 游戏的解读。

解答：

将 Bob 视为一个区分器（distinguisher）：给定样本，输出"Heads"（猜测）或"Tails"（猜测）。

Bob 输的概率：

（最后由 Lemma 50.1。）故 Bob 的最优胜率：

且由 Scheffé 集合的测试恰好达到此上界。

Problem 2：直接用 Hoeffding 证明 Corollary 51.1

题目：直接用 Hoeffding 不等式证明：估计硬币偏置到加法误差，需个样本。

解答：

设经验估计量，，则。

由 Hoeffding 不等式（ i.i.d.）：

令，解得。

注：Hoeffding 给出无先验的界；Theorem 51 利用的先验，通过 Chernoff 得到更优的界（时显著改善）。

Problem 3：和距离不满足数据处理不等式

题目：给出反例，证明和不满足数据处理不等式。

解答：

反例：设为偶数，（上的均匀分布），（上的均匀分布，在上概率为 0）。

初始距离：

后处理函数 （即将前元素映射到 1，后映射到 2）：

：
：，

后处理后距离：

（对。）类似地，而（时），同样违反 DPI。

Problem 4：证明 Scheffé 引理（Fact 50.2）

题目：证明。

解答：

设 Scheffé 集合 。

第一步：

第二步：注意到。利用：

故，结合：

第三步：对任意，

故。

Problem 5：次优样本复杂度的两种证明

题目：证明学习分布的两种次优样本复杂度，并说明如何去掉的假设。

解答：

经验分布，。

方法一（Hoeffding，）：

要，只需对所有：。

对每个用 Hoeffding（视为"硬币偏置"），失败概率，需：

Union Bound 后总失败。

方法二（乘法 Chernoff，需，）：

若对所有，则。

由 Chernoff 和，对每个失败概率，需：

去掉假设——与均匀分布混合：

令，取。

，满足假设（）
（因）
由三角不等式，学到误差即学到误差

Problem 6：为何不直接用独立对估计碰撞概率

题目：将个样本分成个独立对来估计，分析所需样本复杂度。

解答：

令，i.i.d.，。

需区分和，间距，均值。

由 Theorem 52，区分这两个硬币偏置需要独立对数量：

比学分布（）还要差！

原因：Algorithm 23 利用所有对，相当于把有效"样本量"平方，才能得到；只取对丢失了这个关键优势。

Problem 7：编程实践——加拿大 Lotto 6/49 数据集

题目：实现总变差距离、经验分布、均匀性测试算法，并对 Lotto 6/49 数据分析。

解答要点：

(a) 总变差距离：

def total_variation(p, q):
    return 0.5 * sum(abs(pi - qi) for pi, qi in zip(p, q))

(b) 经验分布：

def empirical_dist(samples, k):
    counts = [0] * k
    for x in samples:
        counts[x - 1] += 1
    n = len(samples)
    return [c / n for c in counts]

(c) 均匀性测试（Algorithm 23）：

from collections import Counter
def uniformity_test(samples, k, epsilon):
    n = len(samples)
    tau = (1 + 2 * epsilon**2) / k
    counts = Counter(samples)
    # Z = sum_{j} C(N_j, 2) / C(n, 2)
    Z = sum(c * (c-1) for c in counts.values()) / (n * (n-1))
    return "not uniform" if Z >= tau else "uniform"

(e–g) 结果（，）：

经验分布直方图应接近，轻微波动属正常采样噪声。
均匀性测试：较大时输出"uniform"，极小时（如）因样本量限制可能输出"not uniform"；理论上足够，对以上应够用。
经验分布与均匀分布的 TV 距离：由于采样噪声，预期约为。

Problem 8（进阶）：Laplace 估计量

题目：Laplace 估计量（为出现次数）。

(a) 证明是概率分布。
(b) 证明（）。
(c) 证明。
(d) 得出所需样本数。

解答：

(a)：，各。

(b)：由 Cauchy-Schwarz（）：

故。

(c)：展开后化简（）得。

由线性期望：。

由和二项式展开：

故。

(d)：

取使此，与 Theorem 54 相符！

Part 2: Week 11 讲义知识点——概率分布的学习与测试

§0 本讲背景与模型

核心转变：以往算法的输入是确定性的，本讲的输入是未知概率分布 ，只能通过 i.i.d. 采样访问。

设定：

未知分布定义在大小为的离散域上
可以得到个 i.i.d. 样本
目标：用尽量少的来回答关于的问题

三类问题（复杂度从高到低）：

学习（Learning）：输出使（需了解个值）
估计（Estimation）：估计的某个特征（一个数值）
测试（Testing）：判断是否满足某性质（一个比特）

参数：成功概率，精度，域大小。

随机性来源：算法自身随机性 + 采样的随机性（两者都贡献于失败概率）。

§1 总变差距离（Total Variation Distance）

Definition 50.1（总变差距离）：

性质： - 是上的度量（满足三角不等式、对称性、非负性） - 取值于：；支撑集不相交 - 直觉：是从随机画事件时，和最大可能出现的"超额概率"

-far 定义： is -far from 当。

§2 总变差距离的重要性质

Fact 50.1（数据处理不等式，DPI）：

后处理不增大 TV 距离。（, 不满足此性质，见 Problem 3。）

Lemma 50.1（Pearson–Neyman）：

任何给定单个样本来区分和的（可随机）算法，其 I 型和 II 型错误满足：

等号在 Scheffé 集合 处取到。

Alice-Bob 游戏解读：Bob 从单个样本猜 Alice 从哪个分布采样，最优胜率为（Scheffé 集合测试达到）。

Fact 50.2（Scheffé 引理）：

总变差距离距离的一半。这让范数工具（Cauchy-Schwarz、Hölder 等）都可用于分析。

§3 硬币（）的学习与测试

Theorem 51（学习硬币偏置，有先验）：

$个样本（且最优）$

证明思路：经验估计量，用 Chernoff 界（而非 Hoeffding）利用先验，得到对的依赖。

Corollary 51.1（无先验知识）：

$个样本（且最优）$

取，或直接用 Hoeffding 证明。

Theorem 52（测试硬币是否公平）：

区分偏置和（成功概率）：

$个样本（且最优）$

注：测试和学习所需样本数基本相同——对硬币而言，知道"是否公平"与"知道偏置到 "一样难。

Theorem 53（区分"很偏"与"极偏"）：

区分和（成功概率）：

$个样本$

当时远优于学到加法精度（需）。直觉：时约次就会见到一次 Heads。

§4 学习一般分布（）

算法：经验分布（Empirical Distribution Estimator）

是合法概率分布，且可在时间内计算。

方法一（Hoeffding + Union Bound）：对所有同时保证，再用 Scheffé 引理，得：

$（次优，超二次依赖）$

方法二（乘法 Chernoff，假设）：保证，得：

$（次优，线性于但三次依赖）$

Theorem 54（最优学习复杂度）：

$个样本（且最优）$

是，而非（后者是朴素 median trick 给出的）！

§5 Theorem 54 的证明

方法一（子集 Union Bound）：

由，只需对所有个子集控制。

固定：，由 Hoeffding：

取，即。

Union Bound：。

方法二（代理 + Cauchy-Schwarz + Jensen，仅证常数的情形）：

由：

（更精细地：，用 Cauchy-Schwarz 对。）

取，由 Markov 得。

§6 分布测试：Uniformity Testing

问题（Identity Testing）：

已知参考分布，判断未知是否等于或 -far from （以 TV 距离计）：

若：输出 yes（成功概率）
若：输出 no（成功概率）

化归为 Uniformity Testing（）：

Theorem 55（Identity to Uniformity Reduction）：

设有均匀性测试算法（个样本），则可得对任意参考分布的 Identity Testing 算法，用个样本。

即两者在样本复杂度上等价（相差常数因子）。故只需解决均匀性测试。

§7 测试 vs 学习：样本复杂度的鸿沟

基线（先学后测）：个样本（Theorem 54）。

Theorem 56（均匀性测试，最优量级）：

$个样本（且最优，对常数成功概率）$

相比学习的，在的依赖上有平方根改进！

为何是？Birthday Paradox：

若均匀分布在个元素上（），则取个样本时，以高概率所有样本值各不相同（零碰撞），与从采样完全无法区分。故是下界。

§8 Algorithm 23：基于碰撞的均匀性测试

Algorithm 23（Collision-Based Uniformity Tester）：

输入：个 i.i.d. 样本，参数，域大小

步骤：

设阈值
令，计算碰撞统计量：

若：输出 no（不均匀）；否则输出 yes（均匀）

时间复杂度：（给定）

§9 Algorithm 23 的理论分析

碰撞概率（Remark 56.1）：

是碰撞概率的无偏估计量。

关键等式（公式 75）：

两个区分目标：

情形			与的关系
（均匀）
（远离均匀）

从 TV 到的化归（公式 74）：

（Cauchy-Schwarz。）故。

方差分析（推导次优界）：

涉及个相关指示量，按与的重叠分三类：

4 个不同指标（数量）：独立，
3 个不同指标（数量）：
同一对（数量）：

由此计算：

（用范数单调性，以及。）

由 Chebyshev，要使，需（次优分析给出的界）。

精细的方差分析（超出本课范围）给出最优。

§10 最优均匀性测试复杂度

Theorem 57（最优复杂度，含依赖）：

$个样本（且最优）$

注意依赖的奇特形式：对极小的有非平凡的优势。

Remark（更难的变体）：若测试变为""vs""（），即便，也需个样本——远难于均匀性测试。

§11 样本复杂度汇总

问题	最优样本复杂度	关键工具
学习硬币（有先验）		Chernoff，Theorem 51
学习硬币（无先验）		Hoeffding，Corollary 51.1
测试硬币是否公平		Theorem 52（和学习一样！）
区分"很偏"与"极偏"		Chernoff，Theorem 53
学习元分布		Hoeffding + Union Bound，Theorem 54
均匀性/Identity Testing		碰撞统计，Theorem 56/57
"模糊"均匀性测试（两个）		下界，信息论

§12 本章核心概念总结

概念	关键内容
i.i.d. 采样模型	输入 = 分布，访问方式 = 个独立样本
总变差距离
数据处理不等式（Fact 50.1）	后处理不增大 TV 距离；不满足
Pearson-Neyman 引理（Lemma 50.1）	单样本区分错误率；最优测试 = Scheffé 集合
Scheffé 引理（Fact 50.2）	；Scheffé 集合
学习 vs 测试	学习需样本，均匀性测试只需！
Birthday Paradox 下界	测试均匀性需样本（碰撞论证）
碰撞概率	；（均匀）；（远离均匀）
Algorithm 23	计数碰撞，判为不均匀；样本最优
Identity → Uniformity（Theorem 55）	两类测试样本复杂度等价（相差常数倍）

Part 3: Week 11 Quiz 回顾

来源：Canvas Quiz，整理自 5270-questions-organized.md。每题含中英文题目、正确答案及知识点解析。

Question 1

[EN] In learning and testing distributions, we typically assume the probability distribution we get i.i.d. samples from is over a _______ domain.

[CN] 分布学习与测试中，我们通常假设从概率分布获得的 i.i.d. 样本定义在____域上。

选项	答案
Unknown	❌
Continuous	❌
Discrete	✅

知识点：课程中分布均定义在离散有限域（如）上，分布由概率质量函数 PMF 给出。连续域需要概率密度函数，分析完全不同。

Question 2

[EN] The total variation (TV) distance corresponds to the distance between the probability mass functions.

[CN] 总变差（TV）距离对应概率质量函数之间的距离。

选项	答案
True	✅
False	❌

知识点：由 Scheffé 引理（Fact 50.2）：。这是 TV 距离最重要的等价形式，也是 Algorithm 23 分析的基础。

Question 3

[EN] Total variation distance is ________ and ________.

[CN] TV 距离是_且_。

选项	答案
Unbounded/not a metric	❌
Unbounded/a metric	❌
Bounded/a metric	✅
Bounded/not a metric	❌

知识点：TV 距离满足：(1) 有界：（当时为 0，当支撑集不相交时为 1）；(2) 度量：满足非负性、对称性、三角不等式。此外还满足数据处理不等式（DPI）。

Question 4

[EN] The Data Processing Inequality states that "applying the same function to two random variables cannot ________ their statistical distance."

[CN] 数据处理不等式（DPI）指出：对随机变量施加相同函数不会____它们的统计距离。

选项	答案
Decrease	❌
Increase	✅
Change	❌

知识点：DPI（Fact 50.1）：对任意（可测）函数，。直觉：处理后信息只减不增。注意和距离不满足 DPI（Tutorial Problem 3 的反例）。

Question 5

[EN] Learning the bias of an unknown coin to an additive with probability .99 takes ______ independent coin tosses.

[CN] 以加性误差、概率 0.99 学习未知硬币的偏差，需要____次独立抛掷。

选项	答案
	✅
	❌
	❌
	❌

知识点：Corollary 51.1（硬币学习）：学习偏置到加性误差需样本。由 Hoeffding 不等式直接得到：，来自方差量级。

Question 6

[EN] Testing with probability .99 whether an unknown coin is fair or has bias takes ____ independent coin tosses.

[CN] 以概率 0.99 测试未知硬币是否公平或偏差为，需要____次独立抛掷。

选项	答案
	❌
	✅
	❌
	❌

知识点：Theorem 53（硬币测试）：区分 vs ，两者 TV 距离恰好为，需样本。与学习（Q5）复杂度相同——绝对间距对应样本。

Question 7

[EN] Testing with probability .99 whether an unknown coin has bias at most or at least takes ____ independent coin tosses.

[CN] 以概率 0.99 测试未知硬币偏差还是，需要____次独立抛掷。

选项	答案
	❌
	❌
	❌
	✅

知识点：Theorem 52（乘法间距测试）：区分 vs ，间距比为 2 倍，此时 Chernoff 给出界。对比 Q6（绝对间距，需）——乘法间距使样本量减少一个因子。

Question 8

[EN] Learning an unknown probability distribution (over a known domain of size ) to total variation distance with probability .99 takes _______ independent samples.

[CN] 以 TV 距离、概率 0.99 学习未知分布（已知域大小），需要____样本。

选项	答案
	❌
	❌
	✅
	❌

知识点：Theorem 54（分布学习）：。上界：经验分布 + Union Bound over 个子集，每个用 Hoeffding 控制。下界：个独立硬币各需，故总需。

Question 9

[EN] Testing whether an unknown probability distribution (over a known domain of size ) is the uniform distribution vs. at total variation distance at least 1/100 from , with probability .99, takes ______ independent samples.

[CN] 以概率 0.99 测试未知分布（域大小）是否为均匀分布，或距均匀分布 TV 距离至少，需要____样本。

选项	答案
	✅
	❌
	❌
	❌

知识点：Theorem 56/57（均匀性测试）：，固定故为。Algorithm 23 通过碰撞计数区分（均匀）与（远离均匀）。测试比学习（）省了一个因子！

Question 10

[EN] Among all probability distributions over a given domain , the uniform distribution over _________ the collision probability.

[CN] 在所有定义域上的概率分布中，均匀分布 ____碰撞概率。

选项	答案
Minimises	✅
Maximises	❌

知识点：碰撞概率。由 Cauchy-Schwarz：，等号当且仅当（均匀分布）时成立。故均匀分布使碰撞概率最小，等于。

Week 11 Quiz 速查表

题号	核心概念	正确答案
1	离散域	Discrete
2	TV	True
3	TV 性质	Bounded/a metric
4	DPI	Increase（不会增大距离）
5	学习硬币偏差
6	测试硬币公平（绝对间距）
7	测试偏差 vs （乘法间距）
8	学习分布（元素）
9	测试均匀分布
10	均匀分布碰撞概率	Minimises

高频混淆点： - 学习/测试硬币（Q5,Q6）vs 乘法间距测试（Q7）——间距类型不同，复杂度差因子 - 学习分布（Q8）vs 测试均匀（Q9）——测试远比学习省样本 - 均匀分布最小化碰撞概率（Q10）——这是均匀性测试 Algorithm 23 的算法基础

Part 1: Tutorial 11 详细题解

Problem 1（Warm-up）：Pearson–Neyman 引理 → Alice-Bob 游戏

Problem 2：直接用 Hoeffding 证明 Corollary 51.1

Problem 3： 和 距离不满足数据处理不等式

Problem 4：证明 Scheffé 引理（Fact 50.2）

Problem 5：次优样本复杂度的两种证明

Problem 6：为何不直接用独立对估计碰撞概率

Problem 7：编程实践——加拿大 Lotto 6/49 数据集

Problem 8（进阶）：Laplace 估计量

Part 2: Week 11 讲义知识点——概率分布的学习与测试

§0 本讲背景与模型

§1 总变差距离（Total Variation Distance）

§2 总变差距离的重要性质

§3 硬币（）的学习与测试

§4 学习一般分布（）

§5 Theorem 54 的证明

§6 分布测试：Uniformity Testing

§7 测试 vs 学习：样本复杂度的鸿沟

§8 Algorithm 23：基于碰撞的均匀性测试

§9 Algorithm 23 的理论分析

§10 最优均匀性测试复杂度

§11 样本复杂度汇总

§12 本章核心概念总结

Part 3: Week 11 Quiz 回顾

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Week 11 Quiz 速查表

Problem 3：和距离不满足数据处理不等式