生日悖論

**生日問題**是指最少需要幾人，當中兩人同生日的機率才會過半。答案是 23 人，所以 30 人的小學班級中兩人同生日的機率更高。對於 60 人或更多人，機率大於 99%。這問題有時也稱**生日悖論**，但從引起邏輯矛盾的角度來說生日問題並非悖論，它稱作悖論只因這事實與一般直覺相牴觸而已。大多數人會認為 23 人中兩人同生日的機率應該遠小於一半。計算與此相關的機率稱為**生日問題**，在這個問題之後的數學理論已用於設計著名的密碼攻擊方法：生日攻擊。

## 解釋

生日問題可理解成盲射打靶問題。對於 23 人的房，先考慮問題的補集：23 人皆不同生日的機率是多少？首先可讓 23 人依次進入，每人生日都與眾不同的機率依次是 1、 ${\frac {364}{365}}$ 、 ${\frac {363}{365}}$ 、 ${\frac {362}{365}}$ 、 ${\frac {361}{365}}$ 等。先入房的人的生日皆不同的機率很高，前五個是 1× ${\frac {364}{365}}$ × ${\frac {363}{365}}$ × ${\frac {362}{365}}$ × ${\frac {361}{365}}$ =97.3%；而最後入房的幾人就完全不同，他們入房且找不到同生日者的機率是 ${\frac {345}{365}}$ 、 ${\frac {344}{365}}$ 、 ${\frac {343}{365}}$ 。這種機率可看成對靶的盲射：靶有 365 格，其中 17 個左右黑格，其餘白格。假設每槍必中靶並且分布符合幾何概型的話，連射 12 槍左右任何一發都沒有擊中黑格的機率（投射於房間裡的人生日皆不同）是多少？想必大家立即會感覺到這機率十分微小。

理解生日問題的關鍵在於考慮上述「依次入房」模型中最後幾個入房的人「全都沒碰到同生日的人」機率多少。

簡言之，大多數人之所以會認為 23 人中兩人同生日的機率應該遠遠小於 50%，是因為將問題理解為「其他 22 人與_你_同生日的機率」，而非問題真諦「23 人中兩兩之間存在生日相同」。如果有考慮這點，直覺上會將原來的機率乘以 23 _（注意：此算法並不正確）_ ，則會意識到機率很大。

## 機率估計

假設有 _n_ 個人在房內，如果要計算兩人同生日的機率，在不考慮特殊因素如閏年、雙胞胎的前提下，假設一年 365 日出生機率平均分布（現實的出生機率不是平均分布）。

計算機率的方法是，首先找出 p _（_n_）_ 表示 _n_ 人中，每人生日都不同的機率。假如 _n_ > 365，根據鴿巢原理其機率為 0，假設 _n_ ≤ 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}}$

因為第二人不能跟第一人同生日（機率是 364/365），第三人不能跟前兩人同生日（機率是 363/365），依此類推。用階乘可寫成如下形式

　
: ${365! \over 365^{n}(365-n)!}$

_p_(_n_）表示 _n_ 個人中至少兩人同生日的機率

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

_n_≤365，根據鴿巢原理，_n_ 大於 365 時機率為 1。

_n_ 是 23 時機率約 0.507。其他人數的機率用上面算法可得出：

注意所有人都是隨機選出：作為對比，_q_(_n_) 表示房間中有 _n+1_ 人，當中與特定人（比如你）同生日的機率：

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

當 _n_ = 22 時機率只有大約 0.059，約高於十七分之一。如果 _n_ 人中有 50％機率存在某人跟**你**同生日，_n_ 至少要達到 253。注意這數字大大高於 365/2 = 182.5；究其原因是因為房間內可能有些人同生日。

## 數學論證（非數字方法）

保羅・哈莫斯在自傳中認為生日問題只用計算數值來解釋是種悲哀，所以給出了一種概念數學方法的解釋（儘管這方法有一定的誤差）：乘積

$$
\prod _{k=1}^{n-1}\left(1-{k \over 365}\right)
$$

等於 1－_p_（_n_），因此關注第一個 _n_，欲使乘積小於 1/2。由平均數不等式可知：

　
: ${\sqrt[{n-1}]{\prod _{k=1}^{n-1}\left(1-{k \over 365}\right)}}<{1 \over n-1}\sum _{k=1}^{n-1}\left(1-{k \over 365}\right)$

再用已知的 1 到 _n_－1 所有整數和等於 _n_（_n_－1）/2，然後用不等式 1－_x_ < _e_−x，可得到：

　
: $\prod _{k=1}^{n-1}\left(1-{k \over 365}\right)<\left({1 \over n-1}\sum _{k=1}^{n-1}\left(1-{k \over 365}\right)\right)^{n-1}$

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

如果唯若

　
: $n^{2}-n>730\log _{e}2\cong 505.997\dots $

最後一條表達式的值會小於 0.5。其中 loge 表示自然對數，**略小於** 506，如果取 _n_2－_n_=506 就得到 _n_＝23。

在推導中，哈莫斯寫道：

> 這推論是基於數學系學生必須掌握的重要工具。生日問題曾是用來演示純思維如何勝過機械計算的絕妙例子：這些不等式一兩分鐘就寫得出，但乘法運算就要更多時間且更易出錯，無論使用的工具是鉛筆還是老式電腦。計算機不能提供的是理解力、數學才能、或產生更進階、普適化理論的堅實基礎。
> 
> 

然而哈莫斯的推論只顯示**至少**超過 23 人就能保證平等機會下的生日匹配。因為不知道給出的不等式有多強（嚴格、清晰），因此無法藉此計算過程確定 n＝22 是否能讓機率過半；相反，現在任何人都可用 Microsoft Excel 等個人電腦程式在幾分鐘內把整幅機率分布圖畫出來，對問題答案很快就有通盤掌握，一目了然。

## 泛化和逼近

生日問題可以推廣一下：假設有 _n_ 人，每人都隨機從 _N_ 個特定的數中選一個數出來（N 可能是 365 或其他正整數）。

_p_（_n_）表示有兩個人選擇了同樣的數字，這機率多大？

下面的逼近公式可以回答這個問題

　
: $p(n)\sim 1-1/\exp(n^{2}/(2N))$ 。

### 泛化

下面泛化生日問題：給定從符合離散均勻分布的區間 [1,_d_] 隨機取出 _n_ 個整數，至少 2 個數字相同的機率 _p_（_n_;_d_）有多大？

類似的結果可以根據上面的推導得出。

　
: $p(n;d)={\begin{cases}1-\prod _{k=1}^{n-1}\left(1-{k \over d}\right)&n\leq d\\1&n>d\end{cases}}$

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

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

　
: $p(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({1 \over 1-p}\right)}}+{1 \over 2}$ 。

### 舉例

注意：某些值有色，說明逼近**不**總是正確。

## 經驗性測試

生日問題可以用電腦代碼經驗性類比

生日問題也可以用 Microsoft Excel Spreadsheet 類比

當行數達到 23（即人數），可看到機率結果開始過半。

## 應用

生日問題普遍的應用於檢測雜湊函數：_N_- 位長度的雜湊表可能發生碰撞測試次數不是 2N 次而是只有 2N/2 次，這結論用在破解密碼學雜湊函數的生日攻擊中。

生日問題隱含的理論已經在 [Schnabel 1938] 名字叫做捉放法（capture-recapture）的統計試驗得到應用，來估計湖的魚數。

## 不平衡機率

就像上面提到的，現實世界人口的生日並非平均分布，這種非均衡生日機率問題也已解決。

## 近似匹配

此問題的另外一個泛化是求在 n 人中有兩人的生日同在 k 日曆天內的機率。假設有 m 個同等可能的生日。

　
: ${\begin{aligned}p(n,k,m)&=1-{\frac {(m-nk-1)!}{m^{n-1}{\bigl (}m-n(k+1){\bigr )}!}}\end{aligned}}$

能找到兩個人生日相差 k 天或更少的機率高於 50% 所需要的人數：

　
:

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

## 相關條目

* 機率論
* 生日
* 生日攻擊
* 雜湊函數

## 參考文獻

## 外部連結

* http://www.efgh.com/math/birthday.htm （頁面存檔備份，存於網際網路檔案館）
* http://www.teamten.com/lawrence/puzzles/birthday\_paradox.html （頁面存檔備份，存於網際網路檔案館）
* http://science.howstuffworks.com/question261.htm （頁面存檔備份，存於網際網路檔案館）
* http://mathworld.wolfram.com/BirthdayProblem.html （頁面存檔備份，存於網際網路檔案館）
* http://www.atriumtech.com/pongskorn/birthdayparadox/birthdayparadox.htm （頁面存檔備份，存於網際網路檔案館）