009-应用案例-生日问题

知识点概述

生日问题是古典概率论中一个著名的问题，它探讨在一个群体中，至少有两个人拥有相同生日的概率。这个问题的结论常常与人们的直觉相悖，即只需要一个相对较小的群体，就可以有很高的概率发现相同的生日。

教材原文

（生日问题）求任意 r 个人生日各不相同的概率。 解：理解一年365天就是365个盒。r 个人去任意占这365个盒。“生日互不相同”即每盒至多一球。这正是上例的事件 B。于是所求概率为 $P(B)=\frac{\left(\genfrac{}{}{0ex}{}{365}{r}\right)r!}{365^r}=\frac{365\cdot 364\cdots (365-r+1)}{365^r}$ 当 r = 30 时，$P(B)=0.294$；而当 r = 55 时，$P(B)=0.01$。就是说，任意 55 个人，至少有两人生日相同的概率大到 99%，几乎等于必然事件的概率了。

详细解释

• 问题模型:

  • 将 r 个人的生日视为 r 个独立的随机选择，每个选择都有365种可能（忽略闰年）。
  • 这可以看作一个“占位问题”或“球盒模型”：将 r 个不同的球（人）任意放入 n=365 个不同的盒（天）中。

• 计算方法:

  • 直接计算“至少有两人同生日”的概率比较复杂，因为它包含“恰好两人同生日”、“恰好三个人同生日”等多种情况。
  • 采用对立事件: 计算其对立事件 A = “所有r个人的生日都不同”的概率，然后用 1 减去这个概率。
  • 样本空间总数 $n(\Omega )$: 每个人都有365种生日可能，根据乘法原理，r个人总共有 $365^r$ 种可能的生日组合。
  • 事件A的样本点数 $n(A)$: 第1个人有365种选择，第2个人为避免相同只有364种，…，第r个人有 (365-r+1) 种选择。所以 $n(A)=365\times 364\times \cdots \times (365-r+1)=A_{365}^r$。
  • 概率计算:
    • $P(A)=\frac{A_{365}^r}{365^r}$
    • $P(\text{至少两人同生日})=1-P(A)=1-\frac{A_{365}^r}{365^r}$

学习要点

• 逆向思维: 学习在直接计算复杂事件概率困难时，考虑其对立事件是否更容易计算。
• 模型转换: 掌握将实际问题抽象成古典概型中的“球盒模型”或“占位模型”的能力。
• 反直觉结果: 认识到概率论中的一些结论可能与直觉不符，需要通过严谨的数学计算来验证。

实践应用

• 密码学: 生日攻击（Birthday Attack）是一种密码学攻击手段，它利用生日问题背后的概率原理，来寻找哈希函数的碰撞。即找到两个不同的输入，它们的哈希值相同。攻击者不需要遍历整个空间，而是通过较少的尝试次数就能以较高的概率找到碰撞。
• 数据校验: 在数据存储和传输中，用于检测数据重复或冲突的算法设计，也借鉴了生日问题的思想。

关联知识点

• 前置知识:
  • 007-理论方法-古典概型
  • 008-技术实现-计数原理