生日問題

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

答案令人意外，只需要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，則機率為

{\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），依此類推。用階乘可寫成如下形式

{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。其他人數的機率用上面算法可得出：

n	p（n）
10	12%
20	41%
30	70%
50	97%
100	99.99996%
200	99.9999999999999999999999999998%
300	1 −（7×10⁻⁷³）
350	1 −（3×10⁻¹³¹）
≥366	100%

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

注意所有人都是隨機選出：作為對比，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。其中log_e表示自然對數，略小於506，如果取n²－n=506就得到n＝23。

在推導中，哈莫斯寫道：

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

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

泛化和逼近

用公式

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

（紅綫）與真實機率（黑綫）的比較

生日問題可以推廣一下：假設有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}

。

舉例

逼近			估計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]

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

參考文獻

^ 原文：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.0 ^2.1 M. Abramson and W. O. J. Moser (1970) More Birthday Surprises, American Mathematical Monthly 77, 856–858
^ 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 （頁面存檔備份，存於網際網路檔案館）

[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

[abramson-2] 2.0 ^2.1 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）.

[1]

[2]

[3]