COMP5270 Week 2 总结：Concentration Bounds, and Tricks（题解 + 知识点）
课程: 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 以及为什么有效 |