COMP5270 Week 2 总结：Concentration Bounds, and Tricks（题解 + 知识点）

Posted on 2026-05-26 Edited on 2026-06-14 In Course Notes , COMP5270 Word count in article: 11k Reading time ≈ 42 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 2 Lecture Notes + Tutorial 2 Solutions
主题: Markov inequality, Chebyshev inequality, Chernoff bound, Hoeffding bound, probability amplification, Monte Carlo 与 Las Vegas 的转换

Part 1: Tutorial 2 详细题解

这一周的 Tutorial 主要围绕一个核心问题：

随机变量通常会不会离它的期望很远？

这类问题叫 concentration bounds，也就是“集中不等式”。它们用来控制坏事件发生的概率，是分析随机化算法的重要工具。

Tutorial 开头的难度/要求说明

Tutorial 2 开头特别说明：这一周比较 technical、mathematics-oriented，重点是把后面整门课都会用到的离散概率工具练熟。不是每周都会这么“in the weeds”，但这一周的练习很适合打基础。

题目	Tutorial 原文难度/要求	复习时怎么安排
Problem 1	看过 lecture notes 后应该可以尝试并解决	必做，先把 union bound 和独立事件精确概率区分清楚
Problem 2	看过 lecture notes 后应该可以尝试并解决	必做，Markov 推 Chebyshev 是 concentration bounds 的基础推导
Problem 3	主要是练习操作 series 和 sums；比较 tedious，但学习期间最好做一次	做一次即可，重点是熟悉 Poisson 分布的求和技巧
Problem 4	可能有点 boring，但很适合练习 lecture 里的 bounds，并建立什么时候用哪个 bound 的直觉	必做或至少认真读解答，比较 Markov/Chebyshev/Chernoff 的强弱
Problem 5	用来检查 Monte Carlo 和 Las Vegas 算法关系	必做，理解可检测错误如何转成 Las Vegas
Problem 6	用来检查 Monte Carlo 和 Las Vegas 算法关系	必做，重点是组合两个 Monte Carlo 算法来得到 zero-error/Las Vegas 行为
Problem 7	聚焦 probability amplification，并量化提高成功概率的 cost	必做，掌握重复运行如何把错误概率压低
Problem 8	聚焦 probability amplification，并量化提高成功概率的 cost	必做，尤其注意 one-sided error 比 two-sided error 更容易放大
Problem 9	advanced knowledge；technical 但重要，Chernoff bound 的证明技巧很通用	重点题，建议至少完整读懂证明套路
Problem 10	Chernoff lower-tail 的配套推导，属于技术型 concentration 练习	跟 Problem 9 一起复习，重点看参数怎么选
Problem 11	advanced knowledge；technical 但重要，median trick 是必须知道的工具	重点题，理解什么时候用 median trick 以及为什么有效

Problem 1: Union Bound 与独立事件的精确概率

Tutorial 难度/要求: 看过 lecture notes 后应该可以尝试并解决。目标是弄清楚 union bound 给的是上界，而独立事件可以算出精确概率。

题目: 假设是两个独立事件，每个事件发生概率都是。求至少一个事件发生的概率，并和 union bound 比较。再推广到个独立事件。

详细题解:

要求：

也就是“ 或至少发生一个”。

这种“至少一个发生”的题，常用补集：

$至少一个发生一个都不发生$

一个都不发生就是：

因为独立，所以它们的补事件也独立：

而：

所以：

展开：

因此精确答案是：

Union bound 给什么？

Union bound 说：

所以：

比较一下：

Union bound 给的是上界，不一定精确。它忽略了两个事件同时发生时被重复计算的部分。

推广到个独立事件

如果独立，并且每个事件发生概率都是，则：

因为独立：

所以精确答案是：

Union bound 给：

直觉：

精确公式需要独立性。
Union bound 不需要独立性。
当很小时，，所以 union bound 通常够用。

知识点总结:

求“至少一个发生”时，经常先算“一个都不发生”。
独立事件可以用乘法。
Union bound 不要求独立：

Union bound 通常不精确，但非常好用。

Problem 2: 用 Markov 不等式证明 Chebyshev 不等式

Tutorial 难度/要求: 看过 lecture notes 后应该可以尝试并解决。这题是 concentration bounds 的基础证明：把 Markov 用在非负随机变量上。 ![[Pasted image 20260527191410.png]]

题目: Prove Chebyshev's inequality using Markov's inequality.

详细题解:

先回忆两个不等式。

Markov 不等式:

如果，则对任意：

Chebyshev 不等式:

对任意随机变量和任意：

要从 Markov 推 Chebyshev，关键是构造一个非负随机变量。

令：

因为平方一定非负，所以：

可以对使用 Markov。

注意事件：

等价于：

也就是：

所以：

对用 Markov：

而：

所以：

这就是 Chebyshev 不等式。

知识点总结:

Markov 只能用于非负随机变量。
一定非负。
Chebyshev 本质上是对平方偏差使用 Markov。
Chebyshev 控制的是“离期望至少 ”的概率。

Problem 3: Poisson() 的期望和方差

Tutorial 难度/要求: 主要是练习操作 series 和 sums；官方说它比较 tedious，但学习期间最好做一次。重点是会移动求和下标、识别指数级数。 ![[Pasted image 20260527191459.png]]

题目: Compute the expectation and variance of a Poisson() random variable.

若：

则：

(1) 计算期望

根据定义：

代入 Poisson 概率：

项为 0，所以从开始：

因为：

所以：

把一个提出来：

令，则：

而：

为什么这个级数等于？

这是指数函数的 Maclaurin 级数（泰勒展开在处的特例）：因为的任意阶导数仍是，所以，代入泰勒公式即得上式。令，即得。

这也是泊松分布概率归一化的关键：。

所以：

结论：

(2) 计算方差

方差公式：

直接算会麻烦一点，常用技巧是先算：

因为：

所以：

计算：

两项为 0，所以从开始：

因为：

所以：

提出：

令：

为什么算而不是直接算？

阶乘矩技巧：，刚好消掉分子，让级数再次变成。

一步到位：比直接算简洁得多。

还原：由，得。

这是离散分布求二阶矩的常用技巧，尤其当概率质量函数带阶乘时（Poisson、Binomial 都适用）。

因此：

所以：

结论：

知识点总结:

Poisson 分布的期望和方差都等于。
处理阶乘求和时，经常用换元、。
算方差时，通常比直接算更方便。
指数级数：

Problem 4: Binomial 随机变量的尾概率比较

Tutorial 难度/要求: 可能有点 boring，但非常适合练习 lecture 里的 bounds，并建立“什么时候用哪个 bound 更好”的直觉。 ![[Pasted image 20260527194540.png]]

题目: 令。计算或回忆和，并用 Markov、Chebyshev、Chernoff、Hoeffding 比较不同参数下的尾概率。

Binomial 随机变量可以写成：

其中独立同分布。

所以：

什么是 "bound"？

在 Problem 4 以及后续的 concentration inequality 题目中，"bound" 就是"给概率找一个上界/上限"的意思。

具体来说： - "Bound " = "找一个值，使得，然后证明很小" - 也就是"估计/控制概率最大能到多少"，而不需要算出精确值

为什么用 bound？ 精确计算往往需要复杂的求和或组合数（比如二项分布的 PMF）。而 concentration inequalities 只需知道期望、方差等简单信息，就能快速得到一个安全的上界。

例子：用 Chebyshev 得到，意思是"这个概率最多是这个值"。实际概率可能比界小很多，但知道它不超过就够了。

术语	含义
Upper bound（上界）	概率/值不超过多少
Tail bound（尾概率界）	随机变量偏离期望的概率上限
Concentration bound	一系列用来快速获得上界的不等式

Markov、Chebyshev、Chernoff、Hoeffding 本质上都是 tail bound 工具。

(a) 用 Chebyshev Bound

由 Chebyshev：

这里：

并且：

所以：

结论：

(b) ，比较

此时：

要估计：

也就是比期望大一倍：

Markov

因为：

所以：

Chebyshev

方差：

而：

等价于：

所以：

用 Chebyshev：

所以：

Chernoff

Chernoff 上尾形式：

这里：

所以：

代入：

结论：

Hoeffding

Hoeffding 对变量给：

这里：

所以：

结论：

比较

方法	上界	衰减速度
Markov		不随变小
Chebyshev		多项式衰减
Chernoff		指数衰减
Hoeffding		指数衰减

在这个参数下，Chernoff 和 Hoeffding 明显更强。

(c) ，比较

此时：

目标：

Markov

Chebyshev

方差：

要从期望偏到至少，距离是：

所以：

这个上界大于等于 1 时没有意义，因为概率本来就最多是 1。这样的 bound 叫 vacuous bound。

Chernoff

这里：

所以，：

Hoeffding

这里：

当很大时，这接近 1，也几乎没有意义。

精确概率

Binomial 里：

所以：

当大时：

所以：

这个例子说明：不是所有情况下 Chernoff/Hoeffding 都一定最好。参数很稀疏时，Markov 有时反而更简单、更紧。

知识点总结:

Binomial 的期望和方差：

Markov 只用期望，通常弱，但适用范围广。
Chebyshev 用方差，能给双侧偏离概率。
Chernoff/Hoeffding 对独立和有界随机变量非常强，通常给指数级衰减。
如果是常数，尾概率不一定随变小。

Problem 5: 可检测错误的 Monte Carlo 转 Las Vegas

Tutorial 难度/要求: 用来检查你是否理解 Monte Carlo 和 Las Vegas 算法的关系。关键是：如果错误可检测，就可以拒绝错误输出并重试。 ![[Pasted image 20260527203524.png]]

题目: 证明 lecture notes 的 Theorem 8：如果 Monte Carlo 算法最坏运行时间为，失败概率为常数，并且可以在时间检测输出是否错误，则可以构造 Las Vegas 算法，期望运行时间为。

详细题解:

Monte Carlo 算法的特点是：

运行时间一定有界；
可能输出错误。

这里额外给了一个很强的条件：

输出是否错误可以被检测出来。

那就可以一直重复运行，直到得到正确输出为止。

算法：

运行。
检查输出是否正确。
如果正确，返回结果。
如果错误，重新运行。

因为只有检测正确时才返回，所以 永远不会返回错误答案。这就是 Las Vegas 的正确性要求。

现在分析期望时间。

每次运行成本：

失败概率是，成功概率至少是：

设是直到第一次成功需要的运行次数。则：

这是几何分布。

它的期望是：

所以总期望运行时间：

因为是常数，所以：

知识点总结:

Monte Carlo：时间确定，但可能错。
Las Vegas：答案一定对，但时间是随机的。
如果错误可以检测，就可以“重复直到正确”。
重复次数是几何分布，期望是。

Problem 6: 用两个 Monte Carlo 算法构造 Las Vegas 算法

Tutorial 难度/要求: 同样用于检查 Monte Carlo 与 Las Vegas 的转换关系。重点是把两个带错误概率的方向组合起来，得到不会输出错误答案的算法。

题目: 有两个 Monte Carlo 算法和用于决策问题：

若真实答案是 yes，则以至少概率输出 yes，一定输出 yes。
若真实答案是 no，则一定输出 no，以至少概率输出 no。

两个算法最坏运行时间都是。用构造 Las Vegas 算法并分析期望时间。

详细题解:

这题的关键是看哪些输出是“可信的”。

如果输出 yes，能说明什么？

题目说：如果真实答案是 no，则一定输出 no。

所以不可能在 no 实例上输出 yes。

因此：

$输出真实答案是$

如果输出 no，能说明什么？

题目说：如果真实答案是 yes，则一定输出 yes。

所以不可能在 yes 实例上输出 no。

因此：

$输出真实答案是$

算法：

同时运行和，使用独立随机性。
如果输出 yes，则返回 yes。
如果输出 no，则返回 no。
否则，也就是输出 no 且输出 yes，无法判断，重新运行。

正确性：

返回 yes 时，一定是因为输出 yes，所以真实答案一定是 yes。
返回 no 时，一定是因为输出 no，所以真实答案一定是 no。

因此永远正确，是 Las Vegas 算法。

期望时间：

每轮运行和，成本是：

现在看每轮继续重复的概率。

如果真实答案是 yes：

一定输出 yes；
只有当输出 no 时，才无法判断；
而输出 yes 的概率至少，所以输出 no 的概率最多。

如果真实答案是 no：

一定输出 no；
只有当输出 yes 时，才无法判断；
而输出 no 的概率至少，所以输出 yes 的概率最多。

所以无论哪种情况，每轮重复概率都最多是。

因此期望轮数最多：

总期望时间：

知识点总结:

一侧不会犯错的输出可以当作证书。
Las Vegas 算法可以通过“只在确定时输出，否则重试”构造。
期望重复次数用几何级数。

Problem 7: 双侧错误的概率放大

Tutorial 难度/要求: 聚焦 probability amplification，并要求你量化把成功概率放大所需要的重复次数成本。

题目: 随机化算法输出 good/bad，满足：

若是 good，则；
若是 bad，则。

给定，构造，使得：

若是 good，则；
若是 bad，则。

详细题解:

这是典型的 probability amplification。

原算法已经比随机猜好很多：

good 输入时，大概率输出 good；
bad 输入时，小概率输出 good。

自然做法：

独立运行多次，然后多数投票。

算法：

独立运行共次。
得到个输出。
如果超过一半输出 good，则输出 good。
否则输出 bad。

现在选，让错误概率。

情况 1：是 good

令：

$第次运行输出$

则：

令：

则：

错误当且仅当 good 的票数不到一半：

这比期望至少低：

用 Hoeffding：

情况 2：是 bad

此时每次输出 good 的概率最多，所以：

错误当且仅当 good 的票数至少一半：

这比期望至少高：

同样用 Hoeffding：

所以两种情况错误概率都最多：

要让它不超过，只需：

取对数：

因此：

资源和随机比特：

知识点总结:

双侧错误用多数投票放大。
每次运行必须用独立随机比特。
Hoeffding/Chernoff 可以把错误概率降到指数小。
把常数成功率放大到，通常只需要次重复。

Problem 8: 单侧错误的概率放大

Tutorial 难度/要求: 聚焦 one-sided error 的 probability amplification。与 Problem 7 相比，单侧错误通常可以用更直接的 OR/AND 结构来压低错误概率。

题目: 随机化算法输出 good/bad，满足：

若是 good，则；
若是 bad，则。

给定，构造，使得：

若是 good，则；
若是 bad，则。

详细题解:

这题是 one-sided error。

关键观察：

如果算法输出 good，那么输入一定是 good。因为 bad 输入时：

所以 good 输出是可靠证据。

算法：

独立运行共次。
只要有一次输出 good，就输出 good。
如果次全都没有输出 good，就输出 bad。

bad 输入

若是 bad，则每一次都不可能输出 good，所以也不可能输出 good：

good 输入

若是 good，每次输出 good 的概率至少。

失败是指次全部没有看到 good。

单次没有输出 good 的概率最多：

次都失败的概率最多：

要让失败概率，只需：

取对数：

因此：

资源和随机比特：

知识点总结:

单侧错误不需要多数投票。
只要看到一次可靠的 good，就可以输出 good。
失败概率是“连续次都没成功”：

成功率放大到仍然只需要次重复。

Problem 9: Chernoff Bound 的证明思路

Tutorial 难度/要求: advanced knowledge；technical 但重要。Chernoff bound 的证明技巧很通用，课程外很多随机算法分析也会复用这个套路。

题目: 证明简化版 Chernoff bound。设是 i.i.d. 的随机变量，，令：

证明对：

详细题解:

这题的核心技巧是：

对使用 Markov 不等式。

其中是一个可以自由选择的参数。

(a) 指数函数保持不等号

因为在时是递增函数，所以：

等价于：

因此：

(b) 使用 Markov

一定非负，所以可以用 Markov：

由于：

所以：

因为独立：

又因为它们同分布：

于是：

(c) 计算

因为是 Bernoulli()：

$概率概率$

所以：

又：

所以：

(d) 用简化

分子：

用：

得到：

所以：

定义：

则：

(e) 选择最好的

我们希望右边尽可能小，也就是让尽可能大。

求导：

令：

所以：

代入：

因此：

再使用不等式：

得到：

因为：

所以：

知识点总结:

Chernoff bound 的证明核心是对用 Markov。
是自由参数，最后选择最优的。
独立性用于：

叫 moment-generating function，简称 MGF。
Chernoff 给指数级尾界，通常比 Chebyshev 强。

Problem 10: Chernoff Bound 的下尾

Tutorial 难度/要求: 这是 Problem 9 的配套技术练习，重点是会把同一套 MGF/Markov 方法改成 lower-tail 的参数选择。

题目: 用相同方法证明 Chernoff bound 的另一侧：

其中。

题解思路:

上尾用的是，下尾要控制太小，常用。

因为当时，是递减函数：

等价于：

然后对非负随机变量使用 Markov：

利用独立性：

对 Bernoulli()：

接下来同样用：

并选择最优，可以得到：

这题重点不是背推导，而是看结构：

要证明	使用
上尾太大
下尾太小

知识点总结:

控制上尾用。
控制下尾用。
Chernoff 上尾常数是，下尾常数是。
Chernoff 不只适用于 Bernoulli，也可以推广到独立的随机变量。

Problem 11: Median Trick

Tutorial 难度/要求: advanced knowledge；technical 但非常重要。Median trick 是必须知道的工具，最好通过证明理解它什么时候能用、为什么能用。

题目: 对每个输入，有一个未知好区间。算法每次输出一个值，满足：

其中。算法独立运行共次，输出这个结果的中位数。分析输出落在好区间的概率，并选择使成功概率至少。

详细题解:

这题是 median trick，它是多数投票的连续值版本。

多数投票适合 yes/no 输出；median trick 适合数值输出。

算法：

独立运行共次，得到：

输出这些值的中位数：

什么时候中位数会小于？

只有当超过一半的输出都小于时，中位数才会小于。

定义：

则：

中位数小于的坏事件是：

因为，所以在期望的上方。可以用 Chernoff 或 Hoeffding 得到：

什么时候中位数会大于？

同理，只有当超过一半的输出都大于时，中位数才会大于。

定义：

则：

坏事件是：

同样：

用 union bound 合并两个坏事件

输出不在好区间，只有两种可能：

中位数小于；
中位数大于。

所以：

每一项都可以做到。因此总失败概率。

只需要选：

就可以保证：

为什么必须？

因为 median trick 需要“坏值”少于一半。

如果，那么坏值本来就可能占一半以上，中位数就不一定可靠。

知识点总结:

Median trick 是多数投票的数值版。
中位数出错，意味着一半以上样本都偏到同一侧。
用 Chernoff/Hoeffding 控制“一半以上坏样本”的概率。
用 union bound 合并左右两侧坏事件。
重复次数仍然是。

Part 2: Lecture 2 核心知识点（详细版）

1. Markov Inequality：只用期望控制尾概率

Markov 不等式是这一章最基础的 concentration inequality。

Theorem 10 (Markov's inequality). 设是一个非负随机变量，且。则对任意：

直觉：如果平均值很小，那么很大的概率不可能太高。

为什么“非负”是必须的？

Lecture notes 特别强调：这个条件至关重要，没有它不等式就不成立。反例：设以概率取，以概率取，则，但。

例子：如果，那么。

Markov 的优点： - 条件极少，只需要和期望存在； - 适用范围最广。

Markov 的缺点： - 衰减速度只有，通常比较弱； - 不能控制双侧偏离（只能控制“超过”，不能控制“偏离期望”）。

2. Las Vegas → Monte Carlo：用 Markov 截断

Lecture 中给出了一个单向转换：从 Las Vegas 到 Monte Carlo。

Lemma 4.2. 若存在 Las Vegas 算法，期望运行时间为，则存在 Monte Carlo 算法，最坏运行时间为，失败概率最多。

算法的构造：

输入: x
1: 运行 A(x)，但最多运行 100T 步
2: 若 A 在 100T 步内结束，返回 A 的输出    ← 一定正确
3: 否则，返回任意答案                        ← 很可能错误

分析： - 运行时间显然是； - 当到达 Line 2 时，输出一定正确（因为 Las Vegas 只要结束就正确）； - 当到达 Line 3 时，我们假设它错误； - 需要证明超时概率。

令为的实际运行时间，则，且。用 Markov：

关键观察：这个转换只需要知道期望时间，不需要知道分布的其他信息。

3. Monte Carlo → Las Vegas：当失败可被检测时

如果 Monte Carlo 算法在失败时返回 fail（而不是静默地产生错误答案），就可以转成 Las Vegas。

重复:
    运行 Algorithm 3（用新随机比特）
    设 y 为输出
直到 y ≠ fail
返回 y

正确性：只要返回的，就一定是正确中位数。

期望时间分析：

设为循环次数，为每次运行时间。

利用公式：

所以期望运行时间：

Corollary 7.2. 对任意，上述无限重复算法是 Las Vegas 算法，期望时间。

Theorem 8. 更一般地，若 Monte Carlo 算法最坏时间，失败概率为常数，且错误可在时间检测，则可构造 Las Vegas 算法，期望时间。

4. Chebyshev Inequality：用方差控制偏离

Theorem 11 (Chebyshev's inequality). 设满足。则对任意：

如何从 Markov 推导 Chebyshev？

令，则，可以对用 Markov：

Chebyshev 相比 Markov 的优势：

特性	Markov	Chebyshev
非负要求	必须	不需要
控制方向	只能上单侧	双侧偏离
衰减速度
需要信息	期望	期望 + 方差

在 Randomised Median 中的应用：

分析 Randomised Median 时，Markov 不够用。设为样本中小于中位数的元素个数，则，方差。

我们需要证明不太可能小到（即的位置）。偏离量是（当时）。用 Chebyshev：

这就是的来源。同时也解释了为什么设置：它匹配了 Binomial 的标准差的量级。

5. Union Bound：合并坏事件的神器

Lemma 5.1 (Union Bound). 设是可数个事件（不一定独立），则：

为什么 Union Bound 这么好用？

因为完全不需要独立性！在 Randomised Median 中，三个坏事件之间是否有复杂的依赖关系？我们不需要管，直接相加即可：

代价：如果事件很多，union bound 可能太松。但对于常数个小概率事件，它非常精确。

6. Randomised Median 算法完整分析

算法回顾（Algorithm 3）：

输入: 数组 A（n 个不同整数，n 为奇数）
1: 设 Δ = 4√m
2: 从 A 中独立均匀抽样（有放回）m 个元素，形成样本 B
3: 排序 B                          // O(m log m)
4: 取 b = B[m/2 - Δ]，b̄ = B[m/2 + Δ]   // 近似中位数
5: 在 A 中收集满足 b ≤ x ≤ b̄ 的所有 x，形成候选集 C   // O(n)
6: 计算 k = A 中小于 b 的元素个数       // O(n)
7: 计算 ℓ = A 中大于 b̄ 的元素个数      // O(n)
8: 若 k > n/2 或 ℓ > n/2，返回 fail    // 中位数不可能在 C 中
9: 若 |C| > 4nΔ/m + 2，返回 fail       // C 太大，排序太慢
10: 排序 C                            // O(|C| log |C|)
11: 返回 C 中第 (n+1)/2 - k 个元素      // 这就是 A 的中位数

正确性： - 若算法到达 Line 11，返回的元素在 A 中的位置是，确实是中位数。 - 算法从不返回错误答案：要么返回正确中位数，要么返回 fail。

时间复杂度： - Line 3： - Lines 5–7： - Line 10： - 需要且

选择：

为了让两个排序成本都线性，令两者相等：

取，则： - （当，即，对足够大的成立） - -

所以总时间。

失败概率分析：

坏事件：（太靠右）

意味着大于等于 A 的真实中位数。而是中第小的元素，这意味着在个样本中，最多个元素小于 A 的中位数。

设 $第个样本中位数$ ，则，。

。当时，，所以：

$当时$

用 Chebyshev：

坏事件：（太靠左）

由对称性，同样。

坏事件：太大

这是最难的部分。（表示在 A 中的 rank）。要证，只需证：

以为例。设为 A 中最小的个元素（tail elements）。关键观察：如果中来自的元素少于个，则（第小的元素）不可能是中的元素，所以。

设 $第个样本$ ，则，，。

我们想要：。

用 Chebyshev：，所以：

因此：

右端点的分析完全对称，也得到：

所以：

这里用作为最后上界，是为了和的上界保持统一；实际推出来的上界更强。

总结：

Theorem 7. Randomised Median（Algorithm 3）是一个时间的 Monte Carlo 算法，失败概率最多。

7. Probability Amplification：把失败概率从降到

思路：独立重复运行次，只要有一次不 fail 就返回结果。

重复运行 Algorithm 3 共 T 次（每次用独立随机比特）
若某次未返回 fail，返回该次结果
若全部 T 次都 fail，返回 fail

全部次都失败的概率：

解得：

Corollary 7.1. 对任意，上述重复算法是 Monte Carlo 算法，失败概率最多，最坏时间。

关键代价： - 时间增加倍； - 随机比特增加倍。

8. Majority Vote：黑盒算法的概率放大

场景：有一个查询，每次正确概率仅，错误时不会主动告诉你错了。

算法（Algorithm 5）：

独立查询 T 次，得 y₁, ..., y_T ∈ {yes, no}
返回 majority(y₁, ..., y_T)

设 $正确$ ，则，。

多数投票错误正确答案少于一半：。

，偏离量：。

用 Chebyshev 会怎样？

。Chebyshev 给出：

这个 bound 衰减太慢（需要）。

用 Chernoff：

Theorem 9 (Chernoff bound). 设独立取值于，。对任意：

取，，即，所以：

要，只需：

对比： - Chebyshev：需要次； - Chernoff：只需要次。

Chernoff 的指数衰减远强于 Chebyshev 的多项式衰减。

9. Hoeffding Bound：Additive Deviation

Theorem 12 (Hoeffding bound). 设独立，。对任意：

Corollary 12.1（ i.i.d. 情形）：若 i.i.d.，均值，则对任意：

Hoeffding 是 additive bound：控制的是“偏离期望一个绝对量 ”。

10. Chernoff Bound：Multiplicative Deviation

Theorem 13 (Chernoff bound). 设独立取值于，。对任意：

i.i.d. 版本：若 i.i.d.，均值，则：

Chernoff 是 multiplicative bound：控制的是“偏离期望一个比例 ”。

Theorem 14 (Chernoff with bounded expectations). 若只知（上下界），则：

Rule of thumb： - 当时，multiplicative（Chernoff）通常优于 additive（Hoeffding）； - 当是常数时，两者都可以试试。

11. Markov vs Chebyshev vs Hoeffding vs Chernoff：完整对比

Bound	需要什么	控制什么	何时使用
Markov	，知道		信息最少时；Las Vegas → Monte Carlo 截断
Chebyshev	知道		知道方差时；双侧偏离；Randomised Median 采样分析
Hoeffding	独立、有界	Additive:	偏离是绝对量时；均值估计的 additive error
Chernoff	独立、	Multiplicative:	偏离是比例时；变量和的尾概率；概率放大

一句话总结： - Markov：只知道平均值 → 用它； - Chebyshev：知道方差 → 双侧控制； - Hoeffding：偏离是“绝对量 ” → 指数衰减； - Chernoff：偏离是“相对比例 ” → 更强的指数衰减。

12. Median Trick（预告）

Majority vote 只能处理二元输出。对于数值输出（如估计某个量），可以用 median trick：

独立运行次算法，得到个数值估计；
取中位数作为最终输出；
若每次估计有常数概率落在“好区间”，则中位数落在好区间的概率，只需。

原理：中位数出错意味着至少一半样本都偏离到同一侧，这个概率可以用 Chernoff/Hoeffding 控制。

Median trick 是 majority vote 的数值推广，在 streaming 和 sketching 算法中非常常用（后续章节会详细讲）。

Part 3: 本周知识点总表

必背公式

Markov:

Chebyshev:

Union bound:

Hoeffding:

Chernoff upper tail:

Chernoff lower tail:

算法技巧

Las Vegas Monte Carlo
截断运行时间，用 Markov 控制超时概率。
Monte Carlo Las Vegas
如果错误可以检测，就重复直到成功。
Probability amplification
重复独立运行，把常数失败率降到。
Majority vote
对 yes/no 输出，多次运行后取多数。
Median trick
对数值输出，多次运行后取中位数。

做题判断模板

看到题目问“至少一个事件发生”：

$一个都不发生$

或者用：

看到“非负随机变量超过某个值”：

用 Markov。

看到“离期望超过 ”并且知道方差：

用 Chebyshev。

看到“独立变量的和偏离期望”：

优先想 Chernoff 或 Hoeffding。

看到“错误概率从常数降到 ”：

重复次。

看到“输出可检测 fail”：

可以重复直到非 fail，转 Las Vegas。

看到“黑盒 yes/no 但正确率 ”：

多数投票。

看到“数值输出，每次有常数概率落在好区间”：

median trick。

Part 3: Week 2 Quiz 回顾

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

Question 1

The union bound states that, for events E_1,...,E_k, the probability of their union equals the sum of probabilities. | 选项 | 答案 | |:---|:---| | Only if independent | ❌ | | True | ❌ | | False | ✅ | > Union bound 是上界 ≤，不是等号。

Question 2

Markov's inequality applies to every random variable with well-defined expectation. | 选项 | 答案 | |:---|:---| | True | ❌ | | False: needs variance | ❌ | | False: needs non-negative | ✅ |

Question 3

Always possible to convert Las Vegas → Monte Carlo with similar runtime. | 选项 | 答案 | |:---|:---| | True | ✅ | | False | ❌ |

Question 4

Always possible to convert Monte Carlo → Las Vegas with similar runtime. | 选项 | 答案 | |:---|:---| | True | ❌ | | Not that we know of | ✅ |

Question 5

Chebyshev is always stronger than Markov. | 选项 | 答案 | |:---|:---| | False | ✅ | | True | ❌ |

Question 6

51% Monte Carlo → 99.999% with constant factor runtime. | 选项 | 答案 | |:---|:---| | True | ✅ | | False | ❌ | > 重复运行取多数票，指数级提升。

Question 7

Randomised Median → Las Vegas in expected linear time. | 选项 | 答案 | |:---|:---| | False | ❌ | | True | ✅ |

Question 8

Chernoff/Hoeffding error decays... | 选项 | 答案 | |:---|:---| | Exponentially fast | ✅ | | Polynomially fast | ❌ | | Logarithmically fast | ❌ |

Question 9

Monte Carlo with verifiable output → Las Vegas. | 选项 | 答案 | |:---|:---| | True | ✅ | | Only for decision problems | ❌ |

Question 10

Concentration inequalities only for runtime analysis. | 选项 | 答案 | |:---|:---| | True | ❌ | | False | ✅ | > 也用于近似质量、误差界限、采样复杂度。

Week 2 Quiz 速查表

题号	核心概念	正确答案
1	Union bound	False (≤)
2	Markov 前提	non-negative
3	Las Vegas→Monte Carlo	True
4	Monte Carlo→Las Vegas	Not that we know of
5	Chebyshev vs Markov	False
6	51%→99.999%	True
7	Median→Las Vegas	True
8	集中指数衰减	Exponentially fast
9	可验证→Las Vegas	True
10	集中仅运行时	False

高频混淆点： - Union bound 是 ≤ 不是 =（Q1） - Markov 必须非负（Q2） - Las Vegas→Monte Carlo 容易，反方向难（Q3 vs Q4）

Part 1: Tutorial 2 详细题解

Tutorial 开头的难度/要求说明

Problem 1: Union Bound 与独立事件的精确概率

Problem 2: 用 Markov 不等式证明 Chebyshev 不等式

Problem 3: Poisson() 的期望和方差

Problem 4: Binomial 随机变量的尾概率比较

什么是 "bound"？

(a) 用 Chebyshev Bound

(b) ，比较

(c) ，比较

Problem 5: 可检测错误的 Monte Carlo 转 Las Vegas

Problem 6: 用两个 Monte Carlo 算法构造 Las Vegas 算法

Problem 7: 双侧错误的概率放大

Problem 8: 单侧错误的概率放大

Problem 9: Chernoff Bound 的证明思路

Problem 10: Chernoff Bound 的下尾

Problem 11: Median Trick

Part 2: Lecture 2 核心知识点（详细版）

1. Markov Inequality：只用期望控制尾概率

2. Las Vegas → Monte Carlo：用 Markov 截断

3. Monte Carlo → Las Vegas：当失败可被检测时

4. Chebyshev Inequality：用方差控制偏离

5. Union Bound：合并坏事件的神器

6. Randomised Median 算法完整分析

7. Probability Amplification：把失败概率从 降到

8. Majority Vote：黑盒算法的概率放大

9. Hoeffding Bound：Additive Deviation

10. Chernoff Bound：Multiplicative Deviation

11. Markov vs Chebyshev vs Hoeffding vs Chernoff：完整对比

12. Median Trick（预告）

Part 3: 本周知识点总表

必背公式

算法技巧

做题判断模板

Part 3: Week 2 Quiz 回顾

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Week 2 Quiz 速查表

7. Probability Amplification：把失败概率从降到