知识卡片
碰撞概率不同于配对期望
生日碰撞分析有两种不同问题:至少一对相同生日的概率达到 1/2,或相同生日的配对数期望达到 1。
均匀且独立地从 n 天取样时,两者阈值都为 Θ(√n),但常数和具体人数不同;不能把“期望有一对”直接当成“发生概率过半”。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.