生日問題

生日問題（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頁。這一論文證明了當生日按照平均分布，兩個生日相同的機率最小。