生日悖论

概述

生日悖论 是一个著名的概率反直觉现象：在一个房间里只需要 23 人，其中至少两人生日相同的概率就超过 $1/2$。这一结果与大多数人的直觉相悖，因此被称为”悖论”。

定义

生日悖论

假设一年有 $n=365$ 天（忽略闰年），每个人的生日均匀分布在 $1$ 到 $n$ 之间且相互独立。在 $k$ 个人中，至少两人生日相同的概率记为 $p(k)$。生日悖论指出 $p(23)>1/2$，而 $p(50)\approx 0.970$，$p(366)=1$（由鸽巢原理保证）。

核心性质

• 反直觉性：人们通常认为需要远多于 365/2 ≈ 183 人才能使概率达到 1/2，但实际上 23 人就足够了。这是因为我们比较的是所有人对（共 $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ 对），而非仅与某特定生日比较。
• 互补概率计算：计算”至少一对相同”的互补事件”全部不同”更为方便： $p(k)=1-\frac{n}{n}\cdot \frac{n-1}{n}\cdot \frac{n-2}{n}\cdots \frac{n-k+1}{n}=1-\frac{n!}{(n-k)!n^k}$
• 指示器随机变量分析：定义指示器随机变量 $X_{ij}$ 表示第 $i$ 人和第 $j$ 人生日相同，则生日相同的对数为 $X={\sum }_{1\le i<j\le k}{X}_{ij}$。利用 期望的线性性，$E[X]=\left(\genfrac{}{}{0ex}{}{k}{2}\right)\cdot \frac{1}{n}$。
• 实际意义：生日悖论在哈希表冲突分析、密码学（生日攻击）等领域有重要应用，说明了碰撞概率增长的速度远快于直觉预期。

章节扩展

第5章：概率分析与随机化算法

• 5.4 概率分析与指示器随机变量的进一步应用 使用指示器随机变量和期望的线性性对生日悖论进行形式化分析。

参见

• 指示器随机变量
• 期望的线性性