知识卡片
集齐空箱约需调和次数
把每次独立、均匀投出的球装入 b 个箱子。已有 i−1 个非空箱时,命中新箱的概率为 (b−i+1)/b,等到第 i 个新箱出现所需投球数的期望为 b/(b−i+1)。
从第一个新箱累加到全部箱子,总期望为 b(1+1/2+⋯+1/b)=bH_b≈b ln b,其中 H_b 是第 b 个调和数。后期只剩少数空箱时成功概率很低,因此等待时间主导总成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第5章 概率分析和随机算法 · 查看原书依据
This problem is also known as the coupon collector’s problem, which says that if you are trying to collect each of b different coupons, then you should expect to acquire approximately b ln b randomly obtained coupons in order to succeed.
参考来源
- 位置:《算法导论(第4版)》第 5 章 5.4 节(`OEBPS/chapter005.xhtml`,文本字符 [35000, 40000);公式图 Art_P257–P289)。
- 结论依据:5.4.2 节按已有 i−1 个非空箱分阶段;新球落入空箱概率为 (b−i+1)/b,几何等待时间求和为 bH_b。
- 原始内容:This problem is also known as the coupon collector’s problem , which says that if you are trying to collect each of b different coupons, then you should expect to acquire approximately b ln b randomly obtained coupons in order to succeed.