COMP5270 Week 3 总结：Balls in Bins（题解 + 知识点）

Posted on Edited on In , Word count in article: 18k Reading time ≈ 1:07

课程: 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 控制最大值是很通用的技巧

Problem 1: 空箱期望与覆盖时间下界

Tutorial 难度/要求: 读 lecture notes 或看 lecture 后用于检查理解。重点是用 indicator 算空箱期望，并把“还有空箱”转成覆盖时间下界。

题目: 把 个球均匀独立地投入 个箱子。求空箱数量的期望，并由此说明：要让每个箱子至少有 1 个球，需要多少球？

详细题解:

设 为"第 个箱子在 次投掷后仍为空"的事件，定义指示变量：

空箱总数 。

第一步：求 。

第 个箱子是空的，等价于全部 个球都没有落入它。每个球落入第 个箱子的概率是 ，所以不落入它的概率是 。由独立性：

第二步：用期望线性性求 。

第三步：用 上界化。

[详细推导完整版]

第四步：从空箱期望 推导覆盖所需的 。

核心思路：先让"空箱的期望数"降到 。对非负整数值随机变量 （空箱数），由 Markov 不等式：。所以只要 ，全部覆盖就有正概率。

详细推导：

由第三步，空箱期望上界：

我们要它 ，取更强一点（方便算）的条件：：

两边取自然对数：

移项：

两边乘 ：

所以：

才能覆盖全部个箱子

注：为什么 ？ 因为 是主导项， 只是低阶线性项。当 时，，所以 被 淹没。存在常数 使得 对足够大的 成立，因此 。

其中 是 Euler-Mascheroni 常数。所以：

知识点总结:

  1. 指示变量法：把"计数事件个数"的题目，分解成每个事件的概率之和。
  2. 期望线性性：，不要求独立。
  3. 经典不等式： 对所有 成立，特别在 小时很紧。
  4. 极限：，所以 时空箱期望 。
  5. Markov 一步：要让 ，先做 （因为 当 取整数非负值时）。

Problem 2: 设 为投掷直到每个箱子至少有 1 个球所需的次数（即 Coupon Collector 时间）。

Tutorial 难度/要求: 读 lecture notes 或看 lecture 后用于检查理解。这是 coupon collector 的核心题，复习时要会把等待时间拆成多个 geometric 随机变量。 用 Chebyshev 不等式证明对任意 ：

详细题解:

0. 为什么 Coupon Collector 可以分解为几何分布之和？

这是整个分析的核心洞察。把收集过程看作 个"阶段"：

  • 阶段 （）：已经收集到 种不同邮票，正在等第 种新邮票。
  • 的推导：在阶段 ，已有 个箱子被击中，还空着的箱子有 个。每次投球均匀落入 个箱子之一，落入"新箱子"（空箱子）的概率就是空箱子数量除以总箱子数：

空箱子数

  • 每次投球是独立的 Bernoulli 试验，成功概率 。所以等待第 次新邮票所需的次数服从几何分布 。

具体例子（ 种邮票）：

阶段 已收集 还缺 空箱子数 期望等待
1 0 5 5 1
2 1 4 4
3 2 3 3
4 3 2 2
5 4 1 1 5

关键观察： - 阶段 1：，任何结果都是新邮票，期望等 1 次 - 阶段 （最后一种）：，只剩一种没收集，每次只有 概率命中，期望等 次！

这就是为什么 Coupon Collector 时间是 而不是 ——最后几种稀有邮票等得久，各阶段期望之和 累积出 。

关键性质： 是相互独立的！为什么？

因为几何分布具有无记忆性（memoryless）：当阶段 结束时（投中一个新箱子），过去的历史（阶段 到 投了多少球）不影响后续的概率。阶段 的"成功概率"只取决于当前状态（还剩 个空箱子），与过去无关。因此各阶段的等待时间是独立的几何随机变量。

总时间：

这就是 Coupon Collector 的"标准分解"。

把 写成几何分布之和。设 = 已经击中 个不同箱子后，投到第 个新箱子所需的球数。

的推导：在阶段 ，已有 个箱子被击中，还空着的箱子有 个。每次投球均匀落入 个箱子之一，所以一次投到"新箱子"（空箱子）的概率就是空箱子数量除以总箱子数：

空箱子数

而且 相互独立（由 memoryless 性质）。

第一步：期望。

（最后一步：当 时，，所以 。）

第二步：方差。

几何分布 的方差是 。

由独立性：

（用了 Basel 问题：。）

第三步：套 Chebyshev。

取 ，那么：

（因为 。）

Chebyshev：

代入：

证毕。

第四步：结果解释。

这个结论告诉我们：Coupon Collector 时间 虽然期望是 ，但它高度集中在期望附近（相对集中度）。具体来说：

  • 期望：
  • 偏离期望超过 的概率只有 （当 时非平凡），当 很大时趋于 0

注意：这里用了 这个保守上界，所以推导要求 才能有 。虽然题目只要求 ，但对于 ，这个 bound 是 trivial 的（，Chebyshev 给出 ）。实际上 Coupon Collector 的尾巴衰减比这快得多——可以用更精细的方法（如 Chernoff bound 或鞅方法）证明：偏离 的概率是 甚至指数级。

为什么方差是 而不是 ？

注意方差上界：

这个方差与期望的平方 相比非常小！标准差 ，而期望 。所以变异系数（Coefficient of Variation）为：

这说明 Coupon Collector 时间虽然绝对波动有 ，但相对波动趋于 0，即高度集中在期望附近。

知识点总结:

  1. 几何分布：，，。
  2. 独立和的方差：（独立时）。
  3. 调和数估计：。
  4. Basel 求和：。
  5. Chebyshev：，只要有二阶矩就能用。
  6. Coupon Collector 关键公式：, 。

Problem 3: 让每个箱子至少有 2 个球

Tutorial 难度/要求: 读 lecture notes 或看 lecture 后用于检查理解。它是在 coupon collector 基础上加一层要求，重点是理解为什么时间尺度会继续增加。

题目: 设 为投掷直到每个箱子至少有 2 个球所需的次数。证明 。

详细题解:

下界: （要求所有箱子各 个，比所有箱子各 个更难），其中 是普通 Coupon Collector。所以 。

上界: 关键是"两阶段策略"。详细来说：

  • 阶段一：等到每个箱子至少有 1 个球。这本身就是一个标准 Coupon Collector，按定义需要 次投掷，期望 。
  • 阶段二：在阶段一完成后，每个箱子都恰好有 1 个球（或更多）。现在我们"假装"阶段一没有发生过，只看每个箱子需要第二次被击中。这等价于：从当前状态（每个箱子至少 1 个球）重新开始，再做一次"每个箱子至少再被击中一次"的 Coupon Collector。

为什么阶段二也服从 的分布？

因为投球过程是无记忆（memoryless）的。每个球独立均匀投入 个箱子，已经投了多少球、每个箱子当前有多少球，不影响下一个球落入哪个箱子的概率分布——它仍然是均匀随机的！

所以阶段二所需的额外投掷次数，与阶段一独立同分布，期望也是 。

期望计算：

由期望线性性（或独立随机变量和的期望）：

更严谨的说法：设 为第 个箱子第一次被击中的等待时间， 为第 个箱子第二次被击中的等待时间。由无记忆性， 与 独立且同分布。总时间为 的某种耦合，但期望上界可以直接用两阶段之和控制。

合起来：

知识点总结:

  1. 耦合 (Coupling) 思想：把复杂随机过程拆成已知过程的"叠加"。
  2. Memoryless：投球过程在任何时刻"忘掉"过去，新一轮的几何变量与历史独立。
  3. 泛化：让每个箱子至少有 个球需要 （高阶展开后，第一项主导，第二项是"内部" coupon collector）。
  4. 下界永远是 trivial 的"更难"包含：本题 是最直接的"做更严格的事 → 至少要做更多"。

Problem 4: Chernoff + Union Bound 证明负载集中

Tutorial 难度/要求: more technical，但 good practice。重点是先对单个箱子的负载用 Chernoff，再对所有箱子用 union bound。

题目: 把 个球独立均匀投入 个箱子。设 为第 个箱子的负载。

  • (a) 求 和 。
  • (b) 说明仅用 Chebyshev 无法给出"所有箱子的负载都接近期望"的 high probability bound。
  • (c) 用 Chernoff bound 改进。
  • (d) 选合适的 ，使得所有箱子的负载都在 区间内，概率 。

详细题解:

每个球独立以 概率落入第 个箱子，所以：

(a) 期望和方差

(b) Chebyshev 不够

对单个箱子，Chebyshev 给：

对 个箱子 union bound：

偏离很远

这个数 （当 ），完全是 trivial 上界 。所以 Chebyshev 不够强。

原因：Chebyshev 只用了二阶矩。Bernoulli 之和的尾巴衰减是指数级的，但 Chebyshev 只能看到 这种多项式衰减。

(c) Chernoff bound

对 ，期望 。乘性 Chernoff bound：

取 ：

这就是指数级的尾衰减（ 的负指数）。

(d) Union bound + 取

对 个箱子 union bound：

要让这 ，需要 ，即 。

取 ：

知识点总结:

  1. 二项分布 = Bernoulli 之和：球落入箱子，每个独立。
  2. 二项分布期望方差： 的均值 ，方差 。
  3. 乘性 Chernoff (双边)：，。
  4. Chebyshev vs Chernoff：Chebyshev 给出 多项式衰减，Chernoff 给出 指数衰减。当要做 项 union bound 时，必须用 Chernoff 才能"吞掉"那个 。
  5. Union Bound 的代价：每多一个项，对失败概率"加一份"，所以单项失败概率必须 才有用。

Problem 5: 非均匀分布下的碰撞

Tutorial 难度/要求: more technical，但 good practice。它训练你不要默认“均匀”，而是直接用概率向量计算碰撞概率。

题目: 设球落入箱子的概率不再均匀，而是按分布 （）。

  • (a) 求 2 个球落入同一箱子的概率。
  • (b) 求 个球的期望碰撞数。

详细题解:

(a) 两个球碰撞概率

记号说明：什么是 ？

是一个概率向量。它的 范数（欧几里得范数）定义为：

把平方拿掉根号就是 ：

所以 只是一个紧凑记号，代表「每个 平方后求和」。

碰撞概率推导：

设球 1 和球 2 独立按分布 投掷。两个球都落入第 个箱子的概率为 。

两球碰撞 = 它们落入同一个箱子，不管哪个箱子。重要的是：各个箱子的碰撞事件是互斥的（两球不可能同时落入两个不同的箱子），所以概率直接相加：

两球碰撞同在第箱同在第箱同在第箱

特别：当 均匀（）时，，恢复经典结果 ✓

最小化：由 Cauchy-Schwarz（或 Lagrange），，等号当且仅当 均匀。所以均匀分布最不容易碰撞。

(b) 个球的期望碰撞数

定义指示变量：对每对球 （）：

球和球落入同一箱子

总碰撞数 。由 (a)，。

由期望线性性：

知识点总结:

  1. 范数与碰撞概率：碰撞概率的本质就是分布的 范数平方 = "自我内积"。
  2. 均匀最优：均匀分布使碰撞概率最小（约束 下， 最小）。
  3. 范数下界：，由 Cauchy-Schwarz 。
  4. 指示变量"对"：当题目问"成对发生事件的数量"时，定义 是标准做法。
  5. 应用：在 hashing 里，一个好的 hash function 应该让 key 的像分布近似均匀，以最小化碰撞。

Problem 6: Power of Two Choices 的直觉证明

Tutorial 难度/要求: 设计为 tutorial 中完成；可以提前看，但不要求自己独立解出。重点是理解多一个随机选择为什么能显著降低最大负载。

题目: 把 个球投入 个箱子，每个球随机选 2 个箱子，投入负载较小的那个。证明最大负载是 （高概率）。

详细题解:

设 = 至少有 个球的箱子数。我们想证：当 时，，即没有箱子的负载 。

关键递推：

设 = "成为某个箱子的第 个球"的球数（也就是落入此箱子时，使该箱子从 个球变成 个球的球数）。

显然 （每个负载 的箱子，必有一球是它的第 个球）。

(a)

很简单：每个负载 的箱子至少占 2 个球，所以 。

(b) ：见上。

(c) 第 个球落入"已有 球"箱子的概率

第 个球独立选 2 个箱子（均匀随机），两个都是"已有 球"的箱子时，它的最终落点（较空者）也至少有 球（再加这个球就是第 个）。

设当前 个箱子已有 个球。两个独立选都落到这些箱子的概率：

球成为某箱第个球

（这里 是最终值，过程中 。）

(d) 累加得递推

个球中，每球独立有 概率成为某箱第 个球：

由 （在分析中近似把 看作其期望）：

(e) 解递推

设 （"占比"）。从 出发：

（实际是，因为乘了）

等等，让我们重写。，则 给：

迭代：

要 ，需要 ，即 ，也就是：

所以最大负载 （高概率）。

知识点总结:

  1. 关键直觉：选 2 个随机箱子取较空者 球更不容易跑到"已经很满"的箱子（因为要"两个都满"才会被迫加给一个满的）。
  2. 双随机选择平方效应：概率从 变成 ，造成指数级改进。
  3. 双指数递推：，是双指数衰减。
  4. single choice 对比：单选择最大负载 ；双选择 — 改进巨大。
  5. 应用：分布式 hash table、web 负载均衡器、IP 路由都用这个思想。

Problem 7: 空箱期望趋于

Tutorial 难度/要求: conceptually interesting，simple in hindsight 但不 obvious。可以把它当 puzzle 想，做不出没关系，但一定要看 solution。 ![[Pasted image 20260530225602.png]]

翻译： 个球独立均匀投入 个箱子。证明：当 充分大时，期望空箱数趋近于 。

详细题解:

(1) 期望空箱数公式

由 Problem 1 的线性期望计算（对每个箱子用指示变量，）：

空箱数第个箱子空

推导：每个箱子被一个球"避开"的概率是 ， 个球全部避开该箱子的概率是 。由期望线性性， 个箱子求和即得 。

(2) 核心：证明

目标：

方法（来自官方题解）：利用导数的定义。

第一步，把指数形式取对数（恒等变形）：

所以只需要证明：

令 ，当 时 ，则：

第二步，定义 ，则 。注意到：

这正是 在 处的差商，其极限就是导数 的定义：

第三步，求导：，所以：

因此：

回代：

证毕。

重点：这不仅仅是背公式——它展示了极限 如何通过取对数转化为 的形式，而这个形式正好是 在 处的导数。

(3) 代入得最终结果

空箱数

直觉：把 个球扔到 个箱子里，约有 的箱子是空的，约 恰好 1 个球，剩下 有 个球。

与 Poisson 的联系：箱子里球数近似 分布，。这是 Poissonization 的一个直接应用。

与 Poisson 的联系：箱子里球数近似 分布，。

知识点总结:

  1. 经典极限：。
  2. Poissonization：，所以箱子数近似为 Poisson。
  3. 三分定律： 球 箱时，空箱、单箱、多球箱各占约 。

Problem 8: 澳大利亚彩票

Tutorial 难度/要求: lecture 思想的 real-world application；应该可以自己解决。重点是把彩票问题抽象成 balls-and-bins / coupon collector 风格的概率模型。 ![[Pasted image 20260530225535.png]]

题目: 澳大利亚 X-lotto：从 中选 6 个数字（无序，不重复）。一张票 澳元，奖金 澳元。

  • (a) 中奖概率 是多少？
  • (b) 单张票的期望收益（净盈亏）是多少？
  • (c) 若怀疑彩票"动了手脚"——一半号码组合从不出现，需要观察多少张票才能发现？

详细题解:

(a) 中奖概率 — 详细推导

问题理解：澳大利亚 X-lotto 是从 这 45 个号码中，无顺序、不重复地选出 6 个号码。你买一张票就是猜一组 6 个号码。开奖时随机抽一组 6 个号码，如果你的 6 个号码和开奖结果完全一致（不论顺序），你就中奖。

计数：

从 45 个号码中选 6 个，"选"意味着顺序不重要（即 和 算同一种组合）。这就是组合数：

逐项展开计算：

分子：，，，，

分母：

概率：开奖结果是均匀随机的，你的票只有 1 种组合，总共有 种可能的开奖结果。所以：

中奖

约八百一十四万分之一。作为对比：被闪电击中的概率约 ，中彩票比被雷劈还难 8 倍。

(b) 期望收益 — 详细推导

设随机变量：令 为一张票的奖金收入。 - 中奖时： 澳元，概率 - 不中时：，概率

期望收入：

收入中奖不中澳元

一张票的期望毛收入只有约 12.28 分。

期望净盈亏（减去票价 0.6 澳元）：

净盈亏收入票价澳元

每买一张票，平均亏约 48 分。

为什么要这么算？——期望的定义

期望 = 每个可能结果的值 × 该结果发生的概率，求和。

一张票只有两种可能结果：

结果 净赚（收入 成本） 概率
中奖
不中

按定义直接算净盈亏的期望：

净盈亏

中间 和 恰好消掉，等价于「先算期望毛收入再减票价」。

为什么期望有意义？ 它就是 长期平均。假如你买 次彩票（覆盖所有可能号码各一次），按概率大约中 1 次：

  • 总收入：
  • 总支出：
  • 净亏损：

平均到每次： 澳元——这正是期望值。

100 张票为什么盈利率不变？ 因为期望的线性性：。100 张票的净盈亏就是每张票净盈亏之和，期望自然是 100 倍。比例不变。

核心结论：期望线性性告诉你，「多买」不会改变单位亏损率。彩票的数学决定了买越多亏越多。

买 100 张不同的票（每张选不同号码组合）：

100 张票的成本： 澳元。

因为每张票号码不同，100 张票覆盖了 100 种不同的组合。如果开奖结果落在你覆盖的 100 种之一，你就中奖：

张票中奖

期望收入：

张收入澳元

期望净盈亏：

张净盈亏澳元

关键洞察：

1 张票 100 张票
成本 $0.60 $60.00
期望收入 $ $
期望净盈亏 $ $
盈利率 亏 亏

盈利率完全相同——买多少张都不会改变期望亏损比例。因为：

净盈亏成本

彩票公司的设计保证了：无论你买多少张，长期来看每 1 澳元投入只能收回约 20.5 分。这是彩票盈利的数学基础。

(c) 检测「一半结果消失」— 详细推导

场景：怀疑有一半的号码组合永远不会被摇出，但不知道是哪一半。

题目要求：作为 的函数（大 O 记号），需要观察多少张票才能有统计证据来证明或反驳这个怀疑？

核心洞察：没看到碰撞 = 什么都没学到

假设你观察了 张票，每张都抽到不同的号码组合（没有重复/碰撞）。

  • 公平情形：开奖从 个结果中均匀抽取
  • 作弊情形：开奖只从其中一半（未知哪一半）中均匀抽取

关键事实：在「没有碰撞」的条件下，两种情形下你观察到的序列具有完全相同的概率分布。

直觉：如果你只看到一堆互不相同的号码，你能推断出什么？你看到的只是「某个大小为 的号码子集被抽到了」。在公平情形下，这个大小为 的子集落在「有效一半」里的概率和作弊情形下无法区分——条件于无碰撞，两个假设给出相同的似然。

因此：要想区分两个假设，必须观察到至少一次碰撞。否则任何推断都是徒劳。

用生日悖论求需要的票数

令 为作弊情形下有效结果的数量：（因为 ）。

由生日悖论（见 Theorem 15-16）：在大小为 的空间里随机均匀抽样，大约 次后出现第一次碰撞。

因此：

数值验证

，所以：

即需要约几千张票才可能看到一次碰撞，从而获得区分公平/作弊的统计能力。

总结：题目要求用 big-Oh 作答，答案是 。背后的逻辑链：无碰撞 → 无法区分 → 必须等碰撞 → 生日悖论 → 。

知识点总结:

  1. 彩票总组合数：。
  2. 期望收益：净奖金中奖率票价，对买家几乎总是负的（这是彩票公司的设计）。
  3. 生日悖论 vs 检测：测试均匀性的最敏感统计量之一就是"碰撞数"，因为碰撞数对 极其敏感。
  4. 现象：在 大小的空间随机抽样，约 个样本后出现第一次碰撞。

Problem 9: Poissonization（高级）

Tutorial 难度/要求: Advanced，quite involved，尤其数学计算很 heavy；tutorial 标记为 。复习时重点理解 Poissonization 为什么能让箱子负载变得更容易处理。

题目: 设球落入箱子的分布是 。引入 Poissonization：先取 ，再投 个球。设 是第 个箱子里的球数。

  • (a) 证明 ，并且 相互独立。
  • (b) 把碰撞数 写成 的函数。
  • (c) 求 。
  • (d) 求 。
  • (e) 用 Chebyshev + 多副本平均，推导检测分布偏离均匀需多少球。

详细题解:

(a) 独立 Poisson

关键事实：若 ，把 个 i.i.d. 物品（每个以概率 落入类别 ）分类，则 且 互相独立。

证明思路：

（因为 ，由 。）

最后这个是独立 Poisson 联合密度。证毕。

这是 Poissonization 的"魔术"——把全局约束（）拿掉后，箱子变得完全独立。

(b) 碰撞数

碰撞数 = 每个箱子内部"对"的数量之和：

(c) 期望

由独立性和 ：

Poisson 有 ，所以 ，。

（和 Problem 5(b) 结论一致，差一个 项。）

(d) 方差

由独立性：

对 计算 需要 4 阶矩。Poisson 的累积矩生成函数给出：

阶项

具体计算后（用 ，等等）：

实际严格结果（套 Poisson 的 falling factorial 公式）：

（这里 是 范数立方。）

(e) Chebyshev + 多副本 → 检测复杂度

要区分两个分布 和 的 范数，需要让信号（期望差）超过噪声（标准差）。

如果 均匀（），实验观察 期望 ；如果 不均匀（），期望多了 。

要 Chebyshev 把信号从噪声里区分出来，需要 。再做 个独立副本平均，把方差再除 — 就能在 概率下检测。

总样本数：。

知识点总结:

  1. Poissonization：分类多项式分布 + Poisson 总数 → 独立 Poisson。常用来"去耦合"。
  2. Poisson 矩公式：；；一般地 （factorial moment）。
  3. 碰撞数的方差：，后一项在 大时主导。
  4. 阈值：检测分布是否均匀（差异 ），需要 样本。这是 distribution testing 的基本结果。
  5. 多副本平均：把 个独立估计平均，方差除以 ，标准差除以 — 是经典的 amplification。

Problem 10: 高斯最大值的 MGF 证明

Tutorial 难度/要求: Advanced，quite involved；但这个结果在理论计算机、机器学习和数学里都很常用。重点是学习用 MGF 控制最大值的通用套路。

题目: 设 （不必独立）。证明：

并推出 。

详细题解:

关键技巧（MGF 方法）：

对任意 ：

由于 （每项都 ）：

由 Jensen 不等式（ 是凹函数，）：

关键：这里不需要独立性！因为我们对 取和，而非乘积。

每个 的 MGF：

代入：

优化 ：对 求导令为零：

代回：

证毕。

推论：

把 这 个变量一起取 max：

每个 也是 （高斯对称）。直接用上面的结论：

知识点总结:

  1. MGF 技巧（softmax trick）：。当 大时，。
  2. Jensen 不等式： 凹 。
  3. 高斯 MGF： 的 MGF 是 。
  4. 优化 ：对 形式，，最小值 。
  5. 关键观察：MGF 方法不需要独立性 — 取 max 上界用 sum，sum 的期望可以用 union (sub-additivity)。这是为什么它能处理相依变量。
  6. 阶： 个高斯变量的最大值阶数是 ，远小于 。这一阶在高维概率、统计学习里随处可见。

Part 2: 讲义知识点详解

引言：Balls in Bins 模型

你有 个球，要随机分到 个不同的箱子里。这个看似奇怪的场景捕获了大量的实际应用——hashing、负载均衡、distribution testing、coupon collector 等。

我们关心的三件事：

  1. 最大负载 (Maximum Load)：最满的箱子里有多少球？
  2. 覆盖 (Coverage)：投到多少球后，每个箱子至少有一个？
  3. 碰撞 (Collisions)：有多少对不同的球落入同一个箱子？

最简单的策略：把 个球独立均匀地投到 个箱子里。

一、碰撞 (Collisions) — Birthday Paradox

1.1 核心问题

问：投 个球到 个箱子，至少有一次碰撞（即至少有两个球落入同一个箱子）的概率是多少？

1.2 Theorem 15（生日悖论）— 详细解析

经典描述：

在一个房间里有 23 个人，有约 50% 的概率至少两人同生日。

（注：这里 ，因为 2024 是闰年；2025 年要改成 。）

为什么叫"悖论"？

直觉上，一年有 365 天，需要很多人才能"撞"到同生日。但 23 个人就超过 50%——远小于大多数人猜测的数字。这不是逻辑矛盾，而是直觉和数学之间的冲突：我们习惯线性思维（"要有 个人才覆盖 天"），但碰撞概率是平方增长的。

Balls in Bins 对应：

  • 每个人 = 一个球，一年中的每天 = 一个箱子（共 或 ）
  • "至少两人同生日" = 至少两个球落入同一个箱子 = 至少一次碰撞
  • 问题 = 需要 个人（球）才能使碰撞概率

如何算出 23？

无碰撞的概率：第 1 个人任意生日；第 2 个人避开第 1 人：；第 3 个人避开前 2 人：；依此类推。

无碰撞

代入 ：

无碰撞 至少一次碰撞
10
20
22
23
30
40
60

从 20 人到 30 人，概率从 41% 跳到 71%——碰撞概率增长极为陡峭。

关键直觉：为什么是 ？

不需要精确公式也能看出答案在 量级：

个人产生 对，每对碰撞概率 。当 ，即 ，即 ——期望碰撞数达到 ，碰撞开始"几乎必然"。

对 ：，和精确值 23 在同一个数量级。

定理总结：

项目 内容
问题 个球均匀投入 个箱，至少一次碰撞的概率
精确公式
阈值 时碰撞概率为常数
当 时
渐近（）

1.3 Theorem 16：碰撞概率的精确公式

验证：，。

证明：补集事件是" 个球落入 个不同的箱子"。

直觉：第一个球随便放，第二个球要避开第一个所在的箱子（），第三个要避开前两个所在的箱子（），依此类推。

边界情况： - 若 ，由 Pigeonhole 原理必有碰撞，所以 。 - 若 ，碰撞应该很少见。

1.4 阈值： 时碰撞概率为常数

问题：实验上看， 远在 之前就接近 1。具体在哪个 阶上出现""？是 ？？？还是别的？

答案：。

证明（Stirling 近似法 — 兔子从帽子里跳出来式的证明）：

取 （ 是常数）。由 Stirling 公式 ：

一通"按摩"（massaging）：

代入 ：

三个极限：

  2. （较难，需要二阶展开）

合并得：

即：

特别地：当 时，。

1.5 直觉来源：期望碰撞数

上面的证明像变魔术，没给直觉。这里给一个更直观的推导。

第 1 步：两个球碰撞概率。

第一球落入第 个箱子，第二球要落入同一个箱子，概率 。所以：

更正式地，记 为两球的位置（i.i.d.，均匀分布在 ）：

第 2 步：期望碰撞数 。

把总碰撞数拆成指示变量之和。 个球，任选两个不同的球 （），定义：

球和球落入同一个箱子否则

总碰撞数 = 所有球对的碰撞之和：

所有无序对

有多少对？ 个球中选 2 个 — 这正是组合数 。

每对碰撞的概率： 球 落入某个箱子后，球 独立均匀随机选箱。不管球 在哪，球 有 概率正好选同一个箱子。更正式地：

用期望的线性性求和（不需要球对之间独立！）：

期望线性性对，每对

一句话总结： 是球对数量， 是每对碰撞的概率，线性性把它们乘起来。关键：即使球对之间有复杂的依赖关系，期望线性性照样成立。

第 3 步：阈值出现的位置。

当 时，（期望碰撞数为常数）。如果碰撞数"不会偏离期望太远"，那么阈值就在这里。

要严格证：仅有期望不够；还要看方差，再套 Markov / Chebyshev。

1.6 引理 16.1：碰撞数 的方差

问题：指示变量 之间不独立（比如 和 都成立 ），所以"方差是方差之和"不成立。

但惊人的事实：仍有简洁公式。

证明：算 。

按对 的关系分三种情况：

Case 1：两对相同（）。指示变量平方 = 指示变量本身：。共 个。

Case 2：两对完全不相交（）。 互相独立：。共 个。

Case 3：两对相交于一个元素（）。此时 形如 ，三个球落入同一个箱子：

共 个。

验算总数： ✓

合并：

代数化简（用 ）：

而 ，所以：

证毕。

奇迹：方差恰好就是"如果指示变量独立时该得到的"答案。这并非通用现象，是因为箱子均匀这个对称性，让交叉项神奇地抵消。

一般情形的补救方法： 1. 若 负相关 (negatively correlated)，则仍有 。 2. 永远成立 — 有时直接用 替换也够用。

1.7 Theorem 17：用 Markov + Chebyshev 证明 阈值

结论：

当

当

下界部分（，碰撞概率小）— 用 Markov / first moment method：

上界部分（，碰撞概率大）— 用 Chebyshev / second moment method：

设 ，则 （ 时可验证）。

由 Chebyshev：

（这里用了 ，即引理 16.1。）

所以 。

这种用 的方法被称为 second moment method。

1.8 碰撞问题的应用

  1. Hashing： 个 hash buckets，若有 个 key，必然有碰撞 — 这是 hash table 设计的核心约束。
  2. Distribution testing (statistics)：通过观察"碰撞数"统计量，可以检测分布是否均匀。
  3. Lower bounds for other problems：很多下界证明都归约到生日悖论。

二、覆盖 (Coverage) — Coupon Collector

2.1 问题

投多少球，才能让 个箱子每个都至少有一个球？记此次数为 。

这就是经典的 coupon collector 问题：你在收集 种不同的卡片，每包随机送一种，期望要买多少包才能集齐？

显然 ，但够了吗？

2.2 直觉：用空箱期望反推

关键计算：投了 球后，期望空箱数？

每个箱子是空的概率：第个箱子空。

由期望线性性：

也就是说，投了 个球后，还有大约 个空箱。

重复论证：再投 球，剩下空箱期望 ；再投 球，；……每次投 球，空箱数减少常数倍。

要把空箱数降到 ，需要 轮，每轮 球，总共 球。

2.3 Theorem 18： 的精确期望

其中 是第 个调和数。

事实 18.1（调和数估计）：

其中 是 Euler-Mascheroni 常数。所以 。

证明：

引入辅助变量 （）= 已击中 个不同箱子后，再额外投到第 个新箱子所需的球数。

特别地：（第一球必中"新"箱子）。

显然 ，由期望线性性：

计算 ：已经击中 个箱子后，下一球击中"新"箱子的概率为：

球一直投到第一次击中新箱子停止 — 这正是参数为 的几何分布：

代入 (23)：

（最后一步换元 。）证毕。

2.4 Theorem 19：方差上界

证明的关键观察（surprisingly）：随机变量 相互独立！

直觉：一旦你已经击中 个箱子，"还需要多少新球击中第 个新箱子"只取决于 和 ，而不取决于此前打了多少球。这就是几何分布的 memoryless property。

由独立性：

几何分布方差： 有 。

代入：

（最后用 Basel 求和 。）证毕。

2.5 推论：high-probability bound

由 Chebyshev，对 ：

所以以概率 ：

2.6 补充：Coupon Collector 的详细直觉与对比

经典形式与 Balls in Bins 的等价：

经典形式：一个集邮者想要收集 种不同的邮票。每次购买，他随机获得一种（每种等概率）。问他平均要买多少次才能集齐全部 种？

等价表述：

Balls in Bins 形式：把 个球随机均匀投入 个箱子，问最少需要多少个球才能让每个箱子都至少有一个球？

两种表述完全等价：邮票种类 = 箱子，每次购买 = 投一个球，收集齐 = 每个箱子都有至少一个球。

的具体例子：

阶段 已收集 还缺 空箱子数 期望等待
1 0 5 5 1
2 1 4 4
3 2 3 3
4 3 2 2
5 4 1 1 5

关键观察：最后阶段 ，只剩一种没收集，每次只有 概率命中，期望等 次！这就是 Coupon Collector 时间是 而不是 的来源——最后几种稀有邮票等得久。

三个问题的对比

问题 设定 典型结果 核心直觉
Birthday Paradox（碰撞） 个箱子， 个球 时出现第一次碰撞 在大小为 的空间里， 个样本后碰撞概率 > 50%
Coupon Collector（覆盖） 个箱子，直到每个都有球 期望 最后几种"稀有"邮票要等很久， 种各等 次
Load Balancing（负载） 个箱子， 个球 最大负载 某些箱子会"运气爆棚"接多个球

记忆口诀：碰撞快（），覆盖慢（），负载居中（ 量级）。

三、负载均衡 (Load Balancing)

3.1 问题

固定 个球投入 个箱子（球数 = 箱数），均匀独立。问：最满的箱子有多少球？

其中 = 第 个箱子的球数，。

直觉先猜一下：每个箱子期望 1 个球。最大负载大概是多少？ - 1？不可能——方差 ，有的箱子会有 2、3 个球 - ？可能，因为独立同分布最大值通常 量级 - ？太大了，仿真不支持

3.2 朴素分析：Chebyshev 给出 — 太弱了

我们能多简单地分析？

每个 ：

取 。由 Chebyshev：

对 个箱子 union bound：

结论： 以至少 的概率成立。

但这是 Chebyshev 能给的极限了。 仿真显示实际最大负载远小于 ：

（Chebyshev 上界） 实际 （仿真）

差距巨大！Chebyshev 只用到二阶矩，尾衰减只有 。二项分布的尾巴实际是指数衰减的（Chernoff），所以 Chebyshev 严重高估了最大负载。

教训：独立同分布 Bernoulli 之和（即 Binomial）用 Chernoff 或更精细的工具分析，Chebyshev 给出的界通常粗糙 量级，离真实值差得远。

3.3 Theorem 20：

真正的答案是一个令人惊讶的量级：

既不是 也不是 ——而是在两者之间的 。

数值感受：

实际

即使 达到万亿，最大负载也只有约 14！这就是 的"慢增长"魔力。

接下来证明上界 和下界 。

3.4 上界证明（核心：union bound + 巧妙的 选择）

3.4.0 为什么不能用 Problem 4 的 Chernoff 方案？

Problem 4 处理的是 个球（超线性多球），Chernoff 给出每个箱子 ，再 union bound 能吞掉那个 。

但这里 （球数 = 箱数）。每个箱子只有期望 个球。Chernoff 的指数衰减因子 当 时只是常数级别——不够快，无法吞掉 union bound 的 倍代价。

因此需要换一套武器：二项系数不等式 + Union Bound + 巧妙的 选择 + 尾和公式。

核心思路：证明对于足够大的 ， 衰减得比 还快（指数套指数的形式），从而 union bound 后整体概率还很收敛。

3.4.1 第 1 步：估计 — 子集计数法

设共有 个球编号为 。 是第 个箱子的球数。

关键观察：若第 箱的球数 ，那么 个球中必然存在某个 元子集 ，其中每一个球都落入了第 个箱子。

注意：这是必要条件，不是充要条件—— 意味着「至少」 个球落入，但可能有更多。不过这恰好给出上界：

中所有球均落入箱子

用 Union Bound（事件不一定独立，但 union bound 不需要独立性！）：

中所有球均落入箱子

对称性：对任意固定的 元子集 ， 中 个球全部落入箱子 的概率为 （每个球独立以 概率选 ）。

的 元子集共有 个。因此：

为什么这样算而不是「」的精确概率？ 因为 union bound over subsets 虽然是粗放缩，但后面搭配二项式系数不等式后会产生 的超指数衰减——结果反而比直接算 Binomial 尾更干净。

3.4.2 事实 20.1：二项系数不等式

Fact 20.1。对 ：

证明草图：

下界：

但更简单的下界：。

上界：用 （来自 Stirling 的简单推论 ）：

学习价值：这个不等式是「阶乘化的二项系数 → 指数衰减」的桥梁。当 时， 比 小得多。

3.4.3 代入化简

用上界 代入 (25.1)：

关键结果：。

注意 被消掉了！这意味着对于充分大的 ，一个箱子收到 个球的概率衰减得比指数还快（ 阶）。

3.4.4 第 2 步：Union Bound 到所有箱子

这里 又回来了——这是 union bound 的代价。但 衰减太快，只要 超过某个门槛， 就被吞掉了。

3.4.5 第 3 步：定义临界 —— 巧妙选择

令 为满足以下条件的最小正整数：

等价地

直觉：这个 是「转折点」—— - 当 ： 的 trivial 上界 就够了 - 当 ： 开始 并且迅速收缩

举个例子：设 。若 ， 很大。若 ，。若 ，。临界 就在 附近。

3.4.6 第 4 步：用尾和公式求 的上界

工具：尾和公式 （ 是非负整数随机变量）。

把求和从 处切开：

第一部分：第二部分：

第一部分：有 项，每项 （trivial 上界），所以：

第二部分：对 用 (27)：

核心放缩：因为 ，所以 （底数更大、指数相同的幂更大）：

等一下，更干净的写法是先拆分：

令 ，则 ，：

现在用 的定义 (28)：。

另外， 时（对大 的确成立），。于是：

合起来：

最终：

这太漂亮了：期望最大负载不超过 ，而 的定义完全由「何时 降到 」决定。剩下的工作就是估计 的渐近阶。

3.4.7 第 5 步：估计

由定义， 是使 的最小整数。因此 不满足：

两边取自然对数（）：

即：

设 来简化：。

这个方程通解是 。我们来验证：

上界方向（）：

设 ，代入 ：

当 很大时， 且 。所以括号 ，整体：

我们需要 ，即 。取 （或任意 的常数）即可。所以 至少可以取到 的量级，说明 也在此量级，即 。

下界方向（）：

由 的定义，它本身满足 ，取 log：

类似论证可得 。

结论：

由 (29) 立即得到：

3.4.8 证明结构总结
Pr[单箱 ≥ ℓ]                    子集计数 + 二项系数不等式
    ↓                           → e^ℓ / ℓ^ℓ
Pr[最大负载 ≥ ℓ]                 Union Bound
    ↓                           → n·e^ℓ / ℓ^ℓ  
临界 ℓ(n) 定义                  使 n·e^ℓ / ℓ^ℓ ≤ 1 的最小 ℓ
    ↓
尾和公式求 E[L]                 切两段：前 ℓ(n) 项用 1，后面用几何级数
    ↓
E[L] ≤ ℓ(n) + 1
    ↓
解 ℓ(n) = Θ(log n / log log n)  u(ln u - 1) = ln n 的渐近解
    ↓
E[L] = O(log n / log log n)

核心洞察： 这种「超指数」衰减是整条证明链的引擎。没有二项系数不等式，我们只会得到 （彻底没用）。正是 把 消掉后留下 ，再被 压下去。

3.5 下界证明（详细版）

上界告诉我们 。下界要证明这个界是紧的：。

下界比上界难——要证明「不能更好了」，必须展示一种情况，使得最大负载必然达到该阶。

(1) 核心思想：Poisson 近似 + 独立性

每个箱子的球数 。当 时，由经典极限：

这里 ，所以 近似 。

关键一步（不严格但直观正确）：假设 近似独立且都 。实际上它们不独立（因为 是固定的），但 Poissonization 告诉我们当 很大时，依赖关系很弱。

(2) 用 Markov 型下界

技巧：（对任意 成立，因为 ，两边取期望）。

我们的策略：

令 为独立近似。则：

（用 的事件比用 的事件更难算；放缩成 只要结果还能 work。）

(3) 计算

单个 Poisson 取 的概率：。

由近似独立性：

（用了 。）

所以：

进一步用 放缩：

(4) 选择 使下界非平凡

我们需要 ，即 ，也就是 。

这正是 。

取 （ 适当小常数），验证 对大 成立：

当 时，，即 成立。

(5) 下界结果

回代：

结合上界 ：

(6) 下界证明中的关键技巧

步骤 技巧
Markov 不等式的「反向」应用（下界期望）
近似 独立 Poissonization / Binomial→Poisson 极限
放缩
Stirling 的弱形式
选 需 ，解对数不等式

注意：这个下界证明不是完全严格的（依赖于 Poisson 近似和独立性假设），但给出了正确阶。严格版本需要处理 的依赖关系——可以用 Poissonization（Problem 9）技术来严格化，但超出了基础课范围。

3.6 替代证明（高级）：MGF 方法

这个证明看似 magical，但有几个非常有用的技巧值得吸收。

第 1 步：引入自由参数 （关键创意：把 替换成 以用线性期望）。

第 2 步：由 Jensen 不等式（ 凹）：

第 3 步：用 （对非负 ）：

第 4 步： 同分布，所以：

第 5 步：用二项分布 MGF 公式：

代入 ：

用 ：

第 6 步：优化 。要使 最小。

用平衡技巧（避免求导）：，所以最小化 约等于 。让 ，即：

代入 (32)：

证毕。这给出 的同阶上界，而且常数显式可见。

四、两选择的力量 — Power of Two Choices

4.1 策略

每个球随机选 2 个箱子，然后放入两个中较空的那个（平局任意打破）。

这看起来微不足道 — 每球只是多看一眼。但效果惊人。

4.2 Theorem 21：最大负载指数级下降

对比：

策略 最大负载 大致量级（）
单选择（标准）
双选择

表面看差别不大，但当 极大时双选择是指数级改进。

4.3 直觉：双指数衰减

设 = 至少有 个球的箱子数。在双选择下：

  • 一个球成为某箱第 个球，要求"它的两次随机选都打在已有 个球的箱子里"。
  • 这个概率约 （平方了！）。

所以期望：

设 ，则 — 这是双指数衰减。

从 出发，迭代得 。要 即 ，需要 ，即 。

4.4 应用

  1. Hash table 设计：cuckoo hashing 的核心思想就是双选择。
  2. 任务调度：分布式系统里把任务分给"看起来更空"的两个服务器之一。
  3. Web 负载均衡：load balancer 选 2 个后端，把请求发给负载更小的那个 — 即 JSQ-2 (join-shortest-queue with 2 samples) 算法。
  4. 网络广播：路由器随机选两个邻居，转发到较空的那个。

核心要点速查表

问题 关键结果 主要工具
碰撞概率 时概率为常数 精确计算 + Stirling 近似
期望碰撞数 （均匀）；（一般） 线性期望
覆盖时间 调和级数 + 几何分布
最大负载（单选择） Chernoff + Union Bound / MGF
最大负载（两选择） 双指数递推
空箱期望 （ 时） 线性期望 +
非均匀碰撞 范数分析
高斯最大值 MGF + Jensen

关键不等式总结

不等式 形式 适用场景
Markov 非负随机变量，一阶矩
Chebyshev 需要二阶矩
Chernoff（乘性，双边） Bernoulli 和，指数尾
MGF 技巧 最大值期望上界
Union Bound 多事件联合
标准放缩 把 化成指数
Cauchy-Schwarz 范数下界

复习建议: 这一周的难点在于熟练掌握各种概率不等式的组合使用（尤其是 Chernoff + Union Bound），以及 MGF 方法的技巧性证明。建议重点理解： 1. 碰撞数 范数 的对应关系（Problem 5, 9） 2. Chebyshev 不够 → 用 Chernoff 的范式（Problem 4） 3. 双随机选择的双指数递推（Problem 6） 4. MGF + Jensen 处理最大值（Problem 10、讲义Theorem 20）

这些技巧在分布式系统、随机化算法、分布检测、高维统计里都极其常用。