知识卡片

普通读书笔记卡 · 3606

碰撞概率不同于配对期望

理解等级:中级

生日碰撞分析有两种不同问题:至少一对相同生日的概率达到 1/2,或相同生日的配对数期望达到 1。

均匀且独立地从 n 天取样时,两者阈值都为 Θ(√n),但常数和具体人数不同;不能把“期望有一对”直接当成“发生概率过半”。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第5章 概率分析和随机算法 · 查看原书依据

      The first analysis, which used only probabilities, determined the number of people required for the probability to exceed 1/2 that a matching pair of birthdays exists, and the second analysis, which used indicator random variables, determined the number such that the expected number of matching birthdays is 1.

    参考来源

    - 位置:《算法导论(第4版)》第 5 章 5.4 节(`OEBPS/chapter005.xhtml`,文本字符 [30000, 35000);公式图 Art_P257–P289)。 - 结论依据:5.4.1 节分别计算至少一对生日相同的概率超过 1/2 与相同生日配对数期望为 1 的阈值,明确两种阈值的具体人数不同。 - 原始内容:The first analysis, which used only probabilities, determined the number of people required for the probability to exceed 1/2 that a matching pair of birthdays exists, and the second analysis, which used indicator random variables, determined the number such that the expected number of matching birthdays is 1.