COMP5270 Week 3 总结：Balls in Bins（题解 + 知识点）
课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 3 Lecture Notes (Balls in Bins) + Tutorial 3 Solutions
主题: Collisions (Birthday Paradox), Coverage (Coupon Collector), Load Balancing, Power of Two Choices
Part 1: Tutorial 3 详细题解
这一周的 Tutorial 围绕一个核心模型：
把
个球随机均匀独立地投入 个箱子。然后问：会不会发生碰撞？多少箱子是空的？最满的箱子多满？要投多少球才能让每个箱子都至少有 1 个？
这套模型出现在 hashing、负载均衡、coupon collector、生日悖论、distributed systems 中。本周的工具箱：指示变量 + 期望线性性 + Markov / Chebyshev / Chernoff / Union Bound + MGF 技巧。
Tutorial 开头的难度/要求说明
Tutorial 3 开头把题目分成了几类：前几题检查你是否理解 balls-and-bins 和 coupon collector；中间几题更 technical；后面 Advanced 题比较重，尤其 Problem 9 的计算量很大。
| 题目 | Tutorial 原文难度/要求 | 复习时怎么安排 |
|---|---|---|
| Problem 1 | 读 lecture notes 或看 lecture 后用于检查理解 | 必做，掌握空箱期望和基本下界直觉 |
| Problem 2 | 读 lecture notes 或看 lecture 后用于检查理解 | 必做，coupon collector 的核心题 |
| Problem 3 | 读 lecture notes 或看 lecture 后用于检查理解 | 必做或至少读懂，理解“每个箱子至少 2 个球”的等待时间 |
| Problem 4 | more technical，但 good practice | 练 Chernoff + Union Bound 的标准组合 |
| Problem 5 | more technical，但 good practice | 练非均匀分布下碰撞概率的计算 |
| Problem 6 | 设计为 tutorial 中完成；可以提前看，但不要求自己独立解出 | 课前先看思路，课上重点跟住 power of two choices 的直觉 |
| Problem 7 | conceptually interesting，simple in hindsight 但不 obvious；当 puzzle 想，做不出也没关系，但要看 solution | 适合当思维题，重点是理解 |
| Problem 8 | lecture 思想的 real-world application；应该可以自己解决 | 必做，彩票题能帮助把概率模型放回真实场景 |
| Problem 9 | Advanced，quite involved，尤其数学计算很
heavy；标记为 |
有时间再做，至少读懂 Poissonization 的目的 |
| Problem 10 | Advanced，quite involved；但结果在理论计算机、机器学习、数学中很有用 | 建议认真读，MGF 控制最大值是很通用的技巧 |