生日问题

生日问题（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}$$

<image>

因为第二人不能跟第一人同生日（概率是$\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。其他人数对应的概率用上述算法可得出：

$n$｜$p(n)$

10｜12%

20｜41%

30｜70%

50｜97%

100｜99.99996%

200｜99.9999999999999999999999999998%

300｜$1 - (7 \times 10^{-73})$

350｜$1 - (3 \times 10^{-131})$

$\ge 366$｜100%

<image>

注意所有人都是随机选出：作为对比，记$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)} < \frac{1}{n-1}\sum_{k=1}^{n-1}\left(1-\frac{k}{365}\right)$$

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

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

$$= \left(1-\frac{n}{730}\right)^{n-1} < \left(e^{-n/730}\right)^{n-1} = e^{-(n^2-n)/730}$$

如果仅当：

$$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 等个人电脑程序在几分钟内把整幅机率分布图画出来，对问题答案一目了然。

## 泛化和逼近

<image>

生日问题可以推广：假设有$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}$$

### 举例

指定概率 $p$｜逼近公式推导 $n$｜估计 $N = 365$

$p$｜$n$ 推广界限｜$n < N = 365$｜$n\downarrow$｜$p(n\downarrow)$｜$n\uparrow$｜$p(n\uparrow)$

0.01｜$(0.14178 \sqrt{N}) + 0.5$｜3.20864｜3｜0.00820｜4｜0.01636

0.05｜$(0.32029 \sqrt{N}) + 0.5$｜6.61916｜6｜0.04046｜7｜0.05624

0.1｜$(0.45904 \sqrt{N}) + 0.5$｜9.27002｜9｜0.09462｜10｜0.11695

0.2｜$(0.66805 \sqrt{N}) + 0.5$｜13.26302｜13｜0.19441｜14｜0.22310

0.3｜$(0.84460 \sqrt{N}) + 0.5$｜16.63607｜16｜0.28360｜17｜0.31501

0.5｜$(1.17741 \sqrt{N}) + 0.5$｜22.99439｜22｜0.47570｜23｜0.50730

0.7｜$(1.55176 \sqrt{N}) + 0.5$｜30.14625｜30｜0.70632｜31｜0.73045 （正确值：$n\downarrow=29$, $n\uparrow=30$）

0.8｜$(1.79412 \sqrt{N}) + 0.5$｜34.77666｜34｜0.79532｜35｜0.81438

0.9｜$(2.14597 \sqrt{N}) + 0.5$｜41.49862｜41｜0.90315｜42｜0.91403 （正确值：$n\downarrow=40$, $n\uparrow=41$）

0.95｜$(2.44775 \sqrt{N}) + 0.5$｜47.26414｜47｜0.95477｜48｜0.96060 （正确值：$n\downarrow=46$, $n\uparrow=47$）

0.99｜$(3.03485 \sqrt{N}) + 0.5$｜58.48081｜58｜0.99166｜59｜0.99299 （正确值：$n\downarrow=56$, $n\uparrow=57$）

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

## 经验性测试

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

```pascal
days := 365;
numPeople := 1;
prob := 0.0;
while prob < 0.5 do
begin
   numPeople := numPeople + 1;
   prob := 1 - ((1 - prob) * (days - (numPeople - 1)) / days);
   writeln('Number of people: ', numPeople);
   writeln('Prob. of same birthday: ', prob);
end;
```

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

人数｜人数对应的生日相同的概率公式

1｜1｜`=1-PERMUT(365,A1)/POWER(365,A1)`

2｜`=A1+1`｜`=1-PERMUT(365,A2)/POWER(365,A2)`

3｜`=A2+1`｜`=1-PERMUT(365,A3)/POWER(365,A3)`

当拉取公式直至行数达到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%，所需的人数表如下：

$k$｜在 $m = 365$ 下所需的 $n$ 人数

0｜23

1｜14

2｜11

3｜9

4｜8

5｜8

6｜7

7｜7

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

## 其它相关错觉机率问题

- 星期二男孩问题：一个两孩家庭有一个男孩，他是星期二出生的，那么另一个孩子也是男孩的机率是多少？答：13/27。

## 参考资料

- 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页。这一论文证明了当生日按照平均分布，两个生日相同的概率最小。