冲突问题
来不及写了. 大概说一下结构. 这节将的是将\(m\)个球投到\(n\)个框里面产生的一系列问题. 主要可以分为三个部分:
- 碰撞问题
- 讨论了在随机将\(m\)个球投入\(n\)个bins的时候, 至少有一个bin中出现两个或者更多球的概率问题
- 利用组合方法推导出碰撞概率公式, 并说明当\(m\simeq \sqrt{n}\)的时候, 碰撞概率迅速上升
- 进一步计算了球对碰撞的期望值和方差, 通过期望的线性性质, Chebyshev和Markov不等式证明碰撞事件的集中性, 确定了当\(m\)为\(\Theta(\sqrt{n})\)的时候碰撞概率达到50%点
- 覆盖问题
- 解决了投掷多少个球才能使所有\(n\)个bins至少有一个球的问题, 也就是著名的coupon collector的问题
- 将整个过程分解为多个阶段: 每个阶段等待下一个未命中的bin被填满的球数, 服从几何分布
- 利用线性期望求和, 证明了总期望投掷次数为\(M(n) = n \cdot H_n\)(\(H_n\)为第\(n\)个调和数), 进而得出\(M(n) = \Theta(n \log n)\)的结论
- 同时, 讨论了投掷次数的方差和集中性, 验证了实验结果与理论分析的一致性
- 负载均衡问题
- 分析了当\(m = n\)时, 各个bin内球数的分布情况, 重点研究了最大负载\(L(n)\)的期望
- 利用每个bin的球数服从Binomial(n, 1/n)分布, 采用联合概率界限(union bound), 矩生成函数和Jensen不等式等方法, 证明了\(L(n) = \Theta((\log n) / (\log\log n))\)
- 除了传统的随机投球方式, 还引入了"两选一"(power of two choices)策略, 即每个球随机选择两个bin并进入较少球的那一个, 从而大幅降低最大负载至\(\log\log n + O(1)\)
- 这部分讨论展示了如何通过简单的策略改进负载均衡效果, 对实际应用(如哈希, 任务调度)具有重要意义