生日問題

生日问题（Birthday problem）是一个机率论中的问题，其叙述为：“需要多少人聚在一起，才能让其中至少两人在同一天生日的机率超过一半？”

答案是只需要23人。这个问题有时被称为“生日悖论”（Birthday paradox），但这并非真正的悖论，只是因为其结论违反了一般人的直觉。大多数人会认为，在23人中两人同生日的机率应该远小于50%。该问题衍生出的数学理论被广泛用于设计一种名为“生日攻击”的密码破解方法。

解释
生日问题可以理解成盲射打靶问题。首先计算：23人皆不同生日的概率是多少？可以想象一间空房间，23人依次进入。每个人进入时，其生日与房间内其他人皆不相同的概率依次为1、\frac{364}{365}、\frac{363}{365}、\frac{362}{365}、\frac{361}{365}等。最先进入房间的人，其生日皆不同的概率很高，前五人的概率乘积为 1 \times \frac{364}{365} \times \frac{363}{365} \times \frac{362}{365} \times \frac{361}{365} \approx 97.3%；而随着房间内人数增加，最后几人进入时找不到同生日者的概率下降至\frac{345}{365}、\frac{344}{365}、\frac{343}{365}。

这种概率可以看作对靶的盲射：靶面上有365个格子，其中约有17个黑格，其余为白格。假设每枪必中靶且落点符合几何概型，连射12枪左右且任何一发都没有击中黑格的概率十分微小。

理解生日问题的关键在于，考虑上述“依次入房”模型中最后几个入房的人“全都没碰到同生日者”的概率。

简言之，大多数人之所以认为23人中两人同生日的概率远远小于50%，是因为将问题误解为“其他22人与特定某个人同生日的概率”，而非问题的真谛——“23人中任意两人之间存在生日相同”。如果考虑到23人之间存在的两两配对组合数量多达253对，直觉上就能意识到发生生日碰撞的概率其实相当大。

概率估计
假设有n个人在房内，计算两人同生日的机率。在不考虑特殊因素如闰年、双胞胎的前提下，假设一年365日的出生概率平均分布（尽管现实中的出生机率并非完全平均）。

首先找出\bar{p}(n)，表示n个人中每人生日都互不相同的概率。假如n > 365，根据鸽巢原理其概率为0；假设n \le 365，则概率为：

:\bar{p}(n) = 1 \cdot \left(1-\frac{1}{365}\right) \cdot \left(1-\frac{2}{365}\right) \cdots \left(1-\frac{n-1}{365}\right) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdots \frac{365-n+1}{365}

因为第二人不能跟第一人同生日（概率是\frac{364}{365}），第三人不能跟前两人同生日（概率是\frac{363}{365}），依此类推。用阶乘可写成如下形式：

:\frac{365!}{365^n (365-n)!}

p(n)表示n个人中至少两人同生日的概率：

:p(n) = 1 - \bar{p}(n) = 1 - \frac{365!}{365^n (365-n)!}

当n \le 365时按上式计算；当n > 365时概率为1。

当n = 23时概率约等于0.507。其他人数对应的概率用上述算法可得出：

注意所有人都是随机选出：作为对比，记q(n+1)表示房间中有n+1人，当中与特定某人（比如你）同生日的概率：

:q(n+1) = 1 - \left(\frac{364}{365}\right)^n

当n = 22时概率只有约0.059（约高于十七分之一）。如果房间内有n人，要使其中存在某人跟你同生日的概率超过50%，n至少要达到253。这与任意两人同生日仅需23人的结果形成了巨大的反差，也是引发“悖论”错觉的根源。

数学论证（非数字方法）
保罗·哈莫斯在自传中认为，生日问题只用计算数值来解释是一种悲哀，因此给出了一种概念数学方法的解释推导。乘积：

:\prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right)

等于1 - p(n)。因此关注第一个使乘积小于\frac{1}{2}的n。由平均数不等式可知：

:\sqrt[n-1]{\prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right)}

再利用已知的1到n-1所有整数和等于n(n-1)/2，代入不等式1-x ，可得到：

:\prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right)

:= \left(1-\frac{n}{730}\right)^{n-1}

如果仅当：

:n^2-n > 730\ln 2 \approx 505.997\dots

最后一条表达式的值会小于0.5。其中\ln表示自然对数。其阈值略小于506，如果取n^2-n=506就得到n=23。

在推导中，哈莫斯写道：

这推论是基于数学系学生必须掌握的重要工具。生日问题曾是用来演示纯思维如何胜过机械计算的绝妙例子：这些不等式一两分钟就写得出，但乘法运算就要更多时间且更易出错，无论使用的工具是铅笔还是老式电脑。计算器不能提供的是理解力、数学才能、或产生更高级、普适化理论的坚实基础。

然而哈莫斯的推论只显示至少超过23人就能保证平等机会下的生日匹配概率过半。因为不知道给出的不等式界限有多严格，无法直接藉此计算过程确定n=22时是否能让机率过半；相反，如今任何人都可以使用 Microsoft Excel 等个人电脑程序在几分钟内把整幅机率分布图画出来，对问题答案一目了然。

泛化和逼近
生日问题可以推广：假设有n人，每人都随机从N个特定的数中选一个数出来（N可能是365或其他正整数）。

记p(n)表示有两人选择了同样数字的概率，下面的逼近公式可以回答这个问题：

:p(n) \sim 1 - \exp\left(-\frac{n^2}{2N}\right)

泛化
下面泛化生日问题：给定从符合连续/离散均匀分布的区间[1, d]中随机取出n个整数，至少2个数字相同的概率p(n; d)有多大？

类似的结果可以根据上面的推导得出：

:p(n;d) = \begin{cases} 1 - \prod_{k=1}^{n-1}\left(1-\frac{k}{d}\right) & n \le d \\ 1 & n > d \end{cases}

:p(n;d) \approx 1 - e^{-\frac{n(n-1)}{2d}}

:n(p;d) \approx \sqrt{2d\ln\left(\frac{1}{1-p}\right)} + \frac{1}{2}

若只探讨特定数值（如自己的生日）被选中的概率q(n;d)，则为：

:q(n;d) = 1 - \left(\frac{d-1}{d}\right)^n

反算问题
反算问题可以表述为：对于确定的概率p：

找出最大的n(p)，满足所有的概率p(n)都小于给出的p；或
找出最小的n(p)，满足所有的概率p(n)都大于指定的p。

这个问题有如下逼近公式：

:n(p) \approx \sqrt{2 \cdot 365\ln\left(\frac{1}{1-p}\right)} + \frac{1}{2}

举例
注意：某些带有洋红色标记的值，说明逼近公式不总是严丝合缝地对应真实情况。

经验性测试
生日问题可以通过计算机代码进行经验性模拟：

days := 365;
numPeople := 1;
prob := 0.0;
while prob

生日问题也可以在 Microsoft Excel 等电子表格软件中进行模拟验证：

当拉取公式直至行数达到23（即人数达到23）时，可以观察到概率结果开始超过50%。

应用
生日问题被广泛应用于检测哈希函数的安全性：一个N位长度的哈希表发生碰撞的预期测试次数不是2^N次，而是只有2^{N/2}次。这一结论被直接用在破解密码学散列函数的生日攻击策略中。

此外，生日问题隐含的理论早已在Schnabel（1938年）提出的捉放法（capture-recapture）统计试验中得到了应用，常用来估计湖泊中的鱼类总数。

不平衡概率
正如前文所述，现实世界人口的生日并非绝对平均分布。然而这种非均衡生日概率问题的数学边界也已得到深入解决与论证。

近似匹配
此问题的另外一个泛化是，求在n人中存在两人的生日同在k个日历天内的概率。假设有m个同等可能的生日。

:p(n,k,m) = 1 - \frac{(m - nk - 1)!}{m^{n-1} (m - n(k+1))!}

若要找到两人生日相差k天或以内，并且使概率高于50%，所需的人数表如下：

这意味着只须随机抽取7个人，找到两人之间生日相差一周内的概率就会过半。

参考资料

Zoe Emily Schnabel: "The estimation of the total fish population of a lake"（某湖中鱼类总量估计），美国数学月刊45（1938年）, 348-352页
M. Klamkin，D. Newman: "Extensions of the birthday surprise"（生日惊喜的扩充）, Journal of Combinatorial Theory 3（1967年）,279-282页。
D. Blom: "a birthday problem"（生日问题），美国数学月刊80（1973年）,1141-1142页。这一论文证明了当生日按照平均分布，两个生日相同的概率最小。

评论 (0)