生日悖论

悖论

问问别人，一场聚会要有多少位客人，才很可能有两人同一天生日，大多数人会说 180 位左右，也就是 365 的一半。真正的答案是 23：这时概率是 50.7%。57 位客人时是 99%。之所以叫悖论，不是因为它自相矛盾，而是因为它与我们的直觉相差太远。

为什么直觉会出错

在一个房间里，我们会不自觉地从自己出发思考：有人和我同一天生日的概率是多少？一年有 365 天，这个概率很小。但这个悖论讲的是房间里所有可能的配对，而不是和某一个特定的人生日相同：A 和 B、B 和 C、A 和 C，以此类推。23 人可以组成 253 个不同的配对，每一对都可能同一天生日。

配对数按平方增长

n 个人可以组成 n × (n − 1) / 2 对：10 人组成 45 对，23 人组成 253 对，57 人组成 1,596 对，100 人组成 4,950 对。每一对同一天生日的概率是 1/365，所以 253 对平均会有 253/365 ≈ 0.69 对生日相同。人数翻倍，配对数大约变成四倍，这就是同一天生日的概率迅速攀升的原因。

逐步计算

最简单的方法是先算出没有人生日相同的概率，再用 100% 减去它。第一个人可以占据任何一天。第二个人与第一个人生日不同的概率是 364/365。第三个人与前两人都不同的概率是 363/365，以此类推。对于 23 人：

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49.3%

既然所有人生日都不同的概率是 49.3%，它的对立事件，即至少有两人同一天生日，概率就是 100% − 49.3% = 50.7%。

和你同一天生日

有人和你同一天生日，是另一个问题。其余 n − 1 个人中，每个人避开你生日的概率是 364/365，所以有人和你同一天生日的概率是 1 − (364/365)ⁿ⁻¹。23 人时只有 5.9%，要有另外 253 人才会超过 50%。在 23 人的群体中，253 对里只有 22 对包括你。

平方根法则与生日攻击

对于 N 种可能性相等的取值，大约抽取 1.2 × √N 次后就很可能出现重复：√365 ≈ 19，而 1.2 × 19 ≈ 23。这一点在计算机安全中非常重要。攻击者利用生日攻击寻找两个密码学哈希值相同的输入，也就是碰撞，例如用来伪造数字签名。由于生日悖论，他们需要的尝试次数比直觉认为的少得多：对于 128 位的哈希，大约是 2⁶⁴ 次，而不是 2¹²⁸ 次。这就是 SHA-256 等现代哈希函数输出很长的原因。

在 PictorX 中探索

打开生日悖论，一组 23 人会在一个圆上逐个出现。每来一个新人，就会和已经在场的每个人连上一条线，说明文字会统计配对数。他们的生日落到日历上，有两个或更多生日的那一天会亮起来。下方，按当前人数算出的概率与已测试的组中出现同一天生日的比例并排显示，图表则显示每种人数下的概率，包括有两人同一天生日和有人和你同一天生日两种情况。你可以逐个添加人，选择 2 到 366 人，最多测试 100,000 组，每秒最多 10,000 组，或者测试每种人数，看点逐渐描出曲线。