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

Posted on 2026-05-26 In Course Notes , COMP5270 Word count in article: 8k Reading time ≈ 29 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，也就是“集中不等式”。它们用来控制坏事件发生的概率，是分析随机化算法的重要工具。

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

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

详细题解:

要求：

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

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

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

一个都不发生就是：

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

而：

所以：

展开：

因此精确答案是：

Union bound 给什么？

Union bound 说：

所以：

比较一下：

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

推广到个独立事件

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

因为独立：

所以精确答案是：

Union bound 给：

直觉：

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

知识点总结:

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

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

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

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

详细题解:

先回忆两个不等式。

Markov 不等式:

如果，则对任意：

Chebyshev 不等式:

对任意随机变量和任意：

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

令：

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

可以对使用 Markov。

注意事件：

等价于：

也就是：

所以：

对用 Markov：

而：

所以：

这就是 Chebyshev 不等式。

知识点总结:

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

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

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

若：

则：

(1) 计算期望

根据定义：

代入 Poisson 概率：

项为 0，所以从开始：

因为：

所以：

把一个提出来：

令，则：

而：

所以：

结论：

(2) 计算方差

方差公式：

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

因为：

所以：

计算：

两项为 0，所以从开始：

因为：

所以：

提出：

令：

因此：

所以：

结论：

知识点总结:

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

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

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

Binomial 随机变量可以写成：

其中独立同分布。

所以：

(a) 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

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

详细题解:

Monte Carlo 算法的特点是：

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

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

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

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

算法：

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

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

现在分析期望时间。

每次运行成本：

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

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

这是几何分布。

它的期望是：

所以总期望运行时间：

因为是常数，所以：

知识点总结:

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

Problem 6: 用两个 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: 双侧错误的概率放大

题目: 随机化算法输出 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: 单侧错误的概率放大

题目: 随机化算法输出 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 的证明思路

题目: 证明简化版 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 的下尾

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

其中。

题解思路:

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

因为当时，是递减函数：

等价于：

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

利用独立性：

对 Bernoulli()：

接下来同样用：

并选择最优，可以得到：

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

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

知识点总结:

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

Problem 11: 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。

如果，那么对任意：

直觉：

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

例如，如果：

那么：

Markov 的优点：

条件很少；
只需要；
只需要知道期望。

Markov 的缺点：

通常比较弱；
衰减只有。

2. Las Vegas 到 Monte Carlo：用 Markov 控制超时

Lecture 里给了一个重要转换。

假设有 Las Vegas 算法：

永远正确；
期望运行时间为。

构造 Monte Carlo 算法：

运行，但最多运行步。
如果在步内结束，就返回它的答案。
如果超时，就随便返回一个答案。

运行时间：

错误只可能发生在超时的时候。

令是的运行时间，则：

用 Markov：

所以失败概率最多是：

结论：

期望时间为的 Las Vegas 算法，可以截断成最坏时间、失败概率常数小的 Monte Carlo 算法。

3. Chebyshev Inequality：用方差控制偏离期望

Chebyshev 不等式：

它比 Markov 多用了一个信息：方差。

方差越小，随机变量越集中在期望附近。

Chebyshev 的特点：

不要求；
控制双侧偏离；
衰减是，比 Markov 的更强；
需要知道方差。

4. Union Bound：不用独立性也能合并坏事件

Union bound：

这在随机化算法分析中非常重要，因为失败通常来自多个坏事件。

比如随机中位数算法中，失败可能来自：

左边界太靠右；
右边界太靠左；
候选集合太大。

只要分别证明：

就能立刻得到：

重点：

Union bound 不需要事件独立。

5. Randomised Median：随机抽样找中位数

Lecture 2 的核心算法是 Randomised Median。

目标：在数组中找中位数。

假设：

是奇数；
所有元素互不相同。

算法思路：

从中独立均匀抽样个元素，形成样本数组。
排序。
取中间附近的两个元素：

其中：

在原数组中保留所有满足：

的元素，形成候选集合。

如果太大，或者中位数不可能在中，则返回 fail。
否则排序，从中取出真正的中位数。

为什么这个算法有机会快？

因为只排序小样本，以及较小的候选集合。

如果采样足够代表原数组，中位数附近的窗口不会太大，就小。

Lecture 最后选择：

这样可以让：

并且：

所以总运行时间是：

失败概率怎么分析？

失败由三个坏事件导致：

：太多元素小于，说明已经跑到中位数右边；
：太多元素大于，说明已经跑到中位数左边；
：候选集合太大，排序会太慢。

分别用 Chebyshev 证明：

再用 union bound：

结论：

$是时间的算法，失败概率最多$

6. Probability Amplification：把失败概率降到

如果一个 Monte Carlo 算法失败概率是常数，比如：

想把失败概率降到任意：

可以独立重复运行。

对 Randomised Median：

重复运行算法次。
只要某次没有返回 fail，就返回它的结果。
如果全部 fail，才返回 fail。

因为每次失败概率最多，且独立，所以全部失败概率最多：

要让它，选择：

所以：

总时间：

这就是 probability amplification。

7. Monte Carlo 到 Las Vegas：当错误可以检测时

如果 Monte Carlo 算法失败时会明确返回 fail，而不是 silently wrong，那么可以改成 Las Vegas。

做法：

一直重复运行 Monte Carlo 算法。
如果输出 fail，就重试。
如果输出非 fail，就返回。

因为非 fail 输出一定正确，所以新算法永远正确。

以 Randomised Median 为例，每次失败概率最多：

所以成功概率至少：

重复次数的期望：

每次运行时间，所以总期望时间：

这说明：

会显式报 fail 的 Monte Carlo 算法，可以通过“重复直到成功”变成 Las Vegas 算法。

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

有些 Monte Carlo 算法不会告诉你自己错了。比如一个黑盒查询，每次回答正确概率只有。

想把正确率提高到，可以用多数投票。

做法：

独立查询次。
每次得到 yes/no。
返回出现次数更多的答案。

设：

$正确答案的次数$

则：

多数投票错误意味着正确答案次数小于一半：

这比期望低了：

用 Chernoff 可以得到：

要让错误概率，只需：

所以：

也就是：

9. Hoeffding Bound

Hoeffding 用于独立且有界的随机变量。

如果独立，则：

下尾也类似：

如果，则：

所以：

Hoeffding 是 additive bound，适合控制“比期望多/少一个绝对量 ”。

10. Chernoff Bound

Chernoff 用于独立的随机变量。

令：

上尾：

下尾：

其中：

Chernoff 是 multiplicative bound，适合控制“比期望多/少一个比例”。

11. Markov vs Chebyshev vs Hoeffding vs Chernoff

Bound	需要什么	控制什么	常见强度
Markov	，知道		弱，但适用广
Chebyshev	知道方差		多项式衰减
Hoeffding	独立、有界	additive deviation	指数衰减
Chernoff	独立、	multiplicative deviation	指数衰减

一句话：

Markov：只知道平均值时用。
Chebyshev：知道方差时用。
Hoeffding：偏离是绝对量时用。
Chernoff：偏离是期望的倍数时用。

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。