生日問題
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() |
生日問題是問最少需要多少人,當中兩人同一天生日的概率才會過半,答案是23人。這問題有時也稱生日悖論,但從引起邏輯矛盾的角度來說生日問題並非悖論,它稱作悖論只因這事實與一般直覺相牴觸而已。大多數人會認為23人中兩人同生日的概率應該遠小於一半。計算與此相關的概率稱為生日問題,在這個問題之後的數學理論已用於設計著名的密碼攻擊方法:生日攻擊。
解釋
[編輯]生日問題可理解成盲射打靶問題。首先計算:23人皆不同生日的概率是多少?可想像一間有23人進入的房間,這23人依次進入,每個進入的人的生日都與房裏其他人的生日不同的概率依次是1、、、、等。先入房的人的生日皆不同的概率很高,前五個是1××××=97.3%;而最後入房的幾人就完全不同,他們入房且找不到同生日者的概率是、、。這種概率可看成對靶的盲射:靶有365格,其中17個左右黑格,其餘白格。假設每槍必中靶並且分佈符合幾何概型的話,連射12槍左右任何一發都沒有擊中黑格的概率(投射於房間裏的人生日皆不同)十分微小。
理解生日問題的關鍵在於考慮上述「依次入房」模型中最後幾個入房的人「全都沒碰到同生日的人」概率多少。
簡言之,大多數人之所以會認為23人中兩人同生日的概率應該遠遠小於50%,是因為將問題理解為「其他22人與你同生日的概率」,而非問題真諦「23人中兩兩之間存在生日相同」。如果有考慮這點,直覺上會將原來的概率乘以23(注意:此算法並不正確),則會意識到概率很大。
概率估計
[編輯]假設有n個人在房內,如果要計算兩人同生日的概率,在不考慮特殊因素如閏年、雙胞胎的前提下,假設一年365日出生概率平均分佈(現實的出生概率不是平均分佈)。
計算概率的方法是,首先找出p(n)表示n人中,每人生日都不同的概率。假如n > 365,根據鴿巢原理其概率為0,假設n ≤ 365,則概率為
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Birthday_Paradox.svg/290px-Birthday_Paradox.svg.png)
因為第二人不能跟第一人同生日(概率是364/365),第三人不能跟前兩人同生日(概率是363/365),依此類推。用階乘可寫成如下形式
p(n)表示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% |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Birthday_paradox.svg/290px-Birthday_paradox.svg.png)
注意所有人都是隨機選出:作為對比,q(n)表示房間中有n+1人,當中與特定人(比如你)同生日的概率:
當n = 22時概率只有大約0.059,約高於十七分之一。如果n人中有50%概率存在某人跟你同生日,n至少要達到253。注意這數字大大高於365/2 = 182.5;究其原因是因為房間內可能有些人同生日。
數學論證(非數字方法)
[編輯]保羅·哈莫斯在自傳中認為生日問題只用計算數值來解釋是種悲哀,所以給出了一種概念數學方法的解釋(儘管這方法有一定的誤差):乘積
等於1-p(n),因此關注第一個n,欲使乘積小於1/2。由平均數不等式可知:
再用已知的1到n-1所有整數和等於n(n-1)/2,然後用不等式1-x < e−x,可得到:
如果僅當
最後一條表達式的值會小於0.5。其中loge表示自然對數,略小於506,如果取n2-n=506就得到n=23。
在推導中,哈莫斯寫道:
這推論是基於數學系學生必須掌握的重要工具。生日問題曾是用來演示純思維如何勝過機械計算的絕妙例子:這些不等式一兩分鐘就寫得出,但乘法運算就要更多時間且更易出錯,無論使用的工具是鉛筆還是老式電腦。計數機不能提供的是理解力、數學才能、或產生更進階、普適化理論的堅實基礎。[1]
然而哈莫斯的推論只顯示至少超過23人就能保證平等機會下的生日匹配。因為不知道給出的不等式有多強(嚴格、清晰),因此無法藉此計算過程確定n=22是否能讓概率過半;相反,現在任何人都可用Microsoft Excel等個人電腦程式在幾分鐘內把整幅概率分佈圖畫出來,對問題答案很快就有通盤掌握,一目了然。
泛化和逼近
[編輯]![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Birthday_paradox_approximation.svg/300px-Birthday_paradox_approximation.svg.png)
生日問題可以推廣一下:假設有n人,每人都隨機從N個特定的數中選一個數出來(N可能是365或其他正整數)。
p(n)表示有兩個人選擇了同樣的數字,這概率多大?
下面的逼近公式可以回答這個問題
- 。
泛化
[編輯]下面泛化生日問題:給定從符合離散均勻分佈的區間[1,d]隨機取出n個整數,至少2個數字相同的概率p(n;d)有多大?
類似的結果可以根據上面的推導得出。
反算問題
[編輯]反算問題可能是:
- 對於確定的概率p…
- …找出最大的n(p)滿足所有的概率p(n)都小於給出的p,或者
- …找出最小的n(p)滿足所有的概率p(n)都大於指定的p。
這問題有如下逼近公式:
- 。
舉例
[編輯]逼近 | 估計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-PERMUT(365,A1)/POWER(365,A1) | |
|
=A1+1 | =1-PERMUT(365,A2)/POWER(365,A2) |
|
=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 = 3650 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 (頁面存檔備份,存於互聯網檔案館)