← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3607

集齐空箱约需调和次数

理解等级:中级

把每次独立、均匀投出的球装入 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 个调和数。后期只剩少数空箱时成功概率很低,因此等待时间主导总成本。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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.