生日問題

數學問題

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

解釋

編輯

生日問題可理解成盲射打靶問題。首先計算:23人皆不同生日的概率是多少?可想像一間有23人進入的房間,這23人依次進入,每個進入的人的生日都與房裏其他人的生日不同的概率依次是1、    等。先入房的人的生日皆不同的概率很高,前五個是1× × × × =97.3%;而最後入房的幾人就完全不同,他們入房且找不到同生日者的概率是   。這種概率可看成對靶的盲射:靶有365格,其中17個左右黑格,其餘白格。假設每槍必中靶並且分佈符合幾何概型的話,連射12槍左右任何一發都沒有擊中黑格的概率(投射於房間裏的人生日皆不同)十分微小。

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

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

概率估計

編輯

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

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

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

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

 

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

 

n≤365,根據鴿巢原理,n大於365時概率為1。

n是23時概率約0.507。其他人數的概率用上面算法可得出:

n pn
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人,當中與特定人(比如你)同生日的概率:

 

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

數學論證(非數字方法)

編輯

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

 

等於1-pn),因此關注第一個n,欲使乘積小於1/2。由平均數不等式可知:

 

再用已知的1到n-1所有整數和等於nn-1)/2,然後用不等式1-x < e−x,可得到:

 
 

如果僅當

 

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

在推導中,哈莫斯寫道:

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

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

泛化和逼近

編輯
 
用公式 (紅綫)與真實概率(黑綫)的比較

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

pn)表示有兩個人選擇了同樣的數字,這概率多大?

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

 

泛化

編輯

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

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

 
              
           
 

反算問題

編輯

反算問題可能是:

對於確定的概率p
…找出最大的np)滿足所有的概率pn)都小於給出的p,或者
…找出最小的np)滿足所有的概率pn)都大於指定的p

這問題有如下逼近公式:

 

舉例

編輯
逼近   估計N =365
p   n推廣 n<N =365   n pn↓)  n pn↑)
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-長度的雜湊表可能發生碰撞測試次數不是2N次而是只有2N/2次,這結論用在破解密碼學雜湊函數生日攻擊中。

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

不平衡概率

編輯

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

近似匹配

編輯

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

 

能找到兩個人生日相差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. ^ 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). 

外部連結

編輯