返回资讯中心
外部精选
软件工程
#开发者实时流

生日悖论:23人中至少两人生日相同的概率超过50%

来源标题:Birthday Problem

生日问题表明,在随机选取的23人中,至少两人生日相同的概率超过50%,这一反直觉结论被称为生日悖论。其原理在于23人可组成253对比较,该概率模型被用于哈希碰撞攻击等密码学场景。该问题一般认为由Harold Davenport于1927年前后提出。

Hacker News 最新doener2026/11/22 · 今天30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

在概率论中,生日问题问的是:在随机选取的 n 个人中,至少有两个人生日相同的概率是多少。生日悖论则指一个反直觉的事实:只需要 23 个人,这个概率就能超过 50%。

生日悖论是一种似非而是的悖论:乍看之下似乎不对,但实际上是真的。虽然只需要 23 个人就能达到 50% 的生日相同概率(这个数字不到一年天数的 1/15)看起来令人惊讶,但考虑到生日比较会在每一对可能的人之间进行,这个结果就更直观了。23 个人时,需要考虑 23×22/2=253 对。

生日问题的现实应用包括一种称为生日攻击的密码学攻击,它利用这个概率模型来降低为哈希函数寻找碰撞的复杂度,以及计算在给定规模的人群的哈希值中存在哈希碰撞的近似风险。

这个问题通常被认为大约在 1927 年由 Harold Davenport 提出,不过他当时并未发表。Davenport 并不自称是其发现者,“因为他无法相信此前竟无人提出过”。[1][2] 生日问题某个版本的首篇发表出自 Richard von Mises,于 1939 年。[3]

那么,一个该规模的随机房间中出现生日相同的频率有多高?

1月1日 1月2日 1月3日 1月4日 1月5日 1月6日 1月7日 1月8日 1月9日 1月10日 1月11日 1月12日 1月13日 1月14日 1月15日 1月16日 1月17日 1月18日 1月19日 1月20日 1月21日 1月22日 1月23日 1月24日 1月25日 1月26日 1月27日 1月28日 1月29日 1月30日 1月31日 2月1日 2月2日 2月3日 2月4日 2月5日 2月6日 2月7日 2月8日 2月9日

当人数达到 23 人或更多时,生日相同的情况就比不相同更可能发生。启用 JavaScript 后即可使用此演示的交互版本。

考虑事件 A:一组 k 个人中没有任何重复的生日;并令互补事件 B 为:一组 k 个人中至少有两个人生日相同。那么这两个事件的概率 P(A) 与 P(B) 满足关系式 P(B) = 1 − P(A)。概率 P(A) 可以用排列的视角计算如下。设 V𝑛𝑟 为 k 个人生日各不相同的总方式数,设 Vt 为 k 个人生日排列(包括可能重复的生日)的总方式数。概率 P(A) 就是这两个量之比,即 V𝑛𝑟 除以 Vt。当 k=23 时,这两个计数为 V𝑛𝑟=365⋅364⋅363⋅⋯⋅(365−22)=365!/(365−23)! 以及 Vt=365⋅365⋅365⋅⋯⋅365=36523, 二者之比为 P(A)=V𝑛𝑟/Vt≈0.492703,于是 P(B)=1−P(A)≈1−0.492703=0.507297(50.7297%)。

生日问题的另一种解法是求一个近似概率:在一组 n 个人中至少有两个人生日相同。为简便起见,通常不考虑闰年、双胞胎、选择偏差以及出生率的季节性和周内变化[4],而是假定有 365 个可能的生日,并且每个人的生日等可能地是其中任何一天,且与组内其他人相互独立。

对于相互独立的生日,生日的均匀分布会使一组人中两人生日相同的概率最小。任何不均匀性都会增加两人生日相同的可能性。[5][6] 然而,现实中的生日分布并没有不均匀到足以带来多大改变:在现实世界中,要让生日相同的概率超过 50%,所需的人数仍是 23,与理论上的均匀分布相同。[7]

目标是计算 P(B),即房间中至少有两人生日相同的概率。不过,计算 P(A′)——即房间中没有任何两人生日相同的概率——更为简单。然后,由于 B 与 A′ 是仅有的两种可能且互斥,故 P(B) = 1 − P(A′)。

以下是 23 个人时 P(A) 的计算。将这 23 个人编号为 1 到 23。所有 23 人生日各不相同这一事件,等同于以下事件的合取:第 2 个人与第 1 个人生日不同;第 3 个人与第 1 个人和第 2 个人生日都不同;依此类推;最后,第 23 个人与第 1 至第 22 个人中任何一人的生日都不同。把这些事件称为事件 2、事件 3,等等。事件 1 是第 1 个人有一个生日,其概率为 1。这个事件合取可以用条件概率来计算:事件 2 的概率是 364/365,因为第 2 个人可以有任何不同于第 1 个人生日的生日。类似地,在事件 2 发生的条件下,事件 3 的概率是 363/365,因为第 3 个人可以取第 1、2 个人尚未占用的任何生日。如此继续,最后在所有先前事件都发生的条件下,事件 23 的概率是 343/365。最后,条件概率原理意味着 P(A′) 等于这些个别概率的乘积:

式 (1) 的各项可以合并得到:

计算式 (2) 得 P(A′) ≈ 0.492703

因此,P(B) ≈ 1 − 0.492703 = 0.507297(50.7297%)。

这一过程可以推广到一组 n 个人,其中 p(n) 是 n 个人中至少两人生日相同的概率。先计算所有 n 个生日各不相同的概率 p(n) 更容易。根据鸽巢原理,当 n > 365 时,p(n) 为零。当 n ≤ 365 时:

其中 ! 是阶乘运算符,(365 n) 是二项式系数,kPr 表示排列。

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →