生日問題

生日問題是一個有趣的數學現象，它探討「需要多少人聚在一起，才能讓其中至少有兩人同一天生日的機率超過一半？」

關於新加坡及亞洲學校數學奧林匹克的題目，請見「謝麗爾的生日」。

答案令人意外，只需要23人。這個問題有時被稱為「生日悖論」，不過這其實並不是真正的悖論，只是因為結果違反了一般人的直覺。大多數人會認為23人中兩人同生日的機率應該遠小於50%。

它衍生出的數學理論被用於設計一種名為「生日攻擊」的密碼破解方法。

解釋

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

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

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

機率估計

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

計算機率的方法是，首先找出p（n）表示n人中，每人生日都不同的機率。假如n > 365，根據鴿巢原理其機率為0，假設n ≤ 365，則機率為

${\displaystyle {\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}}}$

該圖片顯示特定人數對應的2個人生日一樣的機率

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

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

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

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

n≤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×10−73）
350	1 −（3×10−131）
≥366	100%

比較p (n) = 任意兩人同生日的機率；q (n) =和某人同生日的機率

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

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

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

數學論證（非數字方法）

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

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

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

${\displaystyle {\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，可得到：

${\displaystyle \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}}$

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

如果唯若

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

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

在推導中，哈莫斯寫道：

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

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

泛化和逼近

用公式${\displaystyle p(n)\sim 1-1/\exp(n^{2}/(2N))}$（紅綫）與真實機率（黑綫）的比較

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

p（n）表示有兩個人選擇了同樣的數字，這機率多大?

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

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

泛化

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

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

${\displaystyle 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}}}$

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

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

${\displaystyle p(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}}$

反算問題

反算問題可能是：

對於確定的機率p…

…找出最大的n（p）滿足所有的機率p（n）都小於給出的p，或者

…找出最小的n（p）滿足所有的機率p（n）都大於指定的p。

這問題有如下逼近公式：

${\displaystyle n(p)\approx {\sqrt {2\cdot 365\ln \left({1 \over 1-p}\right)}}+{1 \over 2}}$。

舉例

逼近			估計N =365
p	n推廣	n<N =365	n↓	p（n↓）	n↑	p（n↑）
0.01	（0.14178 √N）+0.5	3.20864	3	0.00820	4	0.01636
0.05	（0.32029 √N）+0.5	6.61916	6	0.04046	7	0.05624
0.1	（0.45904 √N）+0.5	9.27002	9	0.09462	10	0.11695
0.2	（0.66805 √N）+0.5	13.26302	13	0.19441	14	0.22310
0.3	（0.84460 √N）+0.5	16.63607	16	0.28360	17	0.31501
0.5	（1.17741 √N）+0.5	22.99439	22	0.47570	23	0.50730
0.7	（1.55176 √N）+0.5	30.14625	30	0.70632	31	0.73045　　　（正確值：n↓=29, n↑=30）
0.8	（1.79412 √N）+0.5	34.77666	34	0.79532	35	0.81438
0.9	（2.14597 √N）+0.5	41.49862	41	0.90315	42	0.91403　　　（正確值：n↓=40, n↑=41）
0.95	（2.44775 √N）+0.5	47.26414	47	0.95477	48	0.96060　　　（正確值：n↓=46, n↑=47）
0.99	（3.03485 √N）+0.5	58.48081	58	0.99166	59	0.99299　　　（正確值：n↓=56, n↑=57）

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

經驗性測試

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

days := 365;
numPeople := 1;
prob := 0.0;
while prob < 0.5 begin
    numPeople := numPeople + 1;
    prob := 1 -((1-prob)*(days-(numPeople-1)) / days);
    print "Number of people: " + numPeople;
    print "Prob. of same birthday: " + prob;
end;

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

	人數	人數對應的生日相同的機率
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（即人數），可看到機率結果開始過半。

應用

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

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

不平衡機率

就像上面提到的，現實世界人口的生日並非平均分布，這種非均衡生日機率問題也已解決。^{[來源請求]}

近似匹配

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

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

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

k	n for m = 365
0	23
1	14
2	11
3	9
4	8
5	8
6	7
7	7

只須隨機抽取7人，找到兩人生日相差一周內的機率就會過半。^[2]

其它相關生日錯覺機率問題

星期二男孩問題：一個兩孩家庭有一個男孩，他是星期二出生的，那麼另一個孩子也是男孩的機率是多少？答：13/27^[3]

參考

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

相關條目

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

參考文獻

1. 原文：The reasoning is based on important tools that all students of mathematics should have ready access to. The birthday problem used to be a splendid illustration of the advantages of pure thought over mechanical manipulation; the inequalities can be obtained in a minute or two, whereas the multiplications would take much longer, and be much more subject to error, whether the instrument is a pencil or an old-fashioned desk computer. What calculators do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories
2. M. Abramson and W. O. J. Moser (1970) More Birthday Surprises, American Mathematical Monthly 77, 856–858
3. Jesper Juul. Tuesday Changes Everything (a Mathematical Puzzle). The Ludologist. [2022-05-01]. （原始內容存檔於2022-01-24）.

外部連結

• 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 （頁面存檔備份，存於網際網路檔案館）