標籤: 暫無標籤

生日悖論是指,如果一個房間里有23個或23個以上的人,那麼至少有兩個人的生日相同的概率要大於50%。這就意味著在一個典型的標準小學班級(30人)中,存在兩人生日相同的可能性更高。對於60或者更多的人,這種概率要大於99%。從引起邏輯矛盾的角度來說生日悖論並不是一種悖論,從這個數學事實與一般直覺相抵觸的意義上,它才稱得上是一個悖論。大多數人會認為,23人中有2人生日相同的概率應該遠遠小於50%。計算與此相關的概率被稱為生日問題,在這個問題之後的數學理論已被用於設計著名的密碼攻擊方法:生日攻擊。

1 生日悖論 -解釋

理解生日悖論的關鍵在於領會相同生日的搭配可以是相當多的。如23個人可以產生C(23,2)= 23 × 22/2 = 253 種不同的搭配,而這每一種搭配都有成功相等的可能。從這樣的角度看,在253種搭配中產生一對成功的配對也並不是那樣的不可思議。

換一個角度,如果你進入了一個有著22個人的房間,房間里的人中會和你有相同生日的概率便不是五十五十了,而是變得非常低。原因是這時候只能產生22種不同的搭配。生日問題實際上是在問任何23個人中會有兩人生日相同的概率是多少。

2 生日悖論 -計算

不計特殊的年月,如閏二月。先計算房間里所有人的生日都不相同的概率,那麼
第一個人的生日是 365選365
第二個人的生日是 365選364
第三個人的生日是 365選363
:
:
:
第n個人的生日是 365選365-(n-1)
所以所有人生日都不相同的概率是:
(365/365)× (364/365) ×(363/365) ×(362/365)× ... ×(365-n+1/365)
那麼,n個人中有至少兩個人生日相同的概率就是:
1-(365/365)× (364/365) ×(363/365) ×(362/365)× ... ×(365-n+1/365)
所以當n=23的時候,概率為0.507
當n=100的時候,概率為0.9999996

3 生日悖論 -測試

生日悖論可以用計算機代碼經驗性模擬:

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;

4 生日悖論 -延伸

此問題另外一個范化就是求得要在隨機選取多少人中才能找到2個人生日相同,相差1天,2天等的概率大於50% 。這是個更難的問題需要用到容斥原理。結果(假設生日依然按照平均分佈)正像在標準生日問題中那樣令人吃驚:

2人生日相差k天 #需要的人數
0                        23
1                        14
2                        11
3                        9
4                        8
5                        7
7                        6

只需要隨機抽取6個人,找到兩個人生日相差一周以內的概率就會超過50%。

5 生日悖論 -應用

生日悖論普遍的應用於檢測哈希函數:N-位長度的哈希表可能發生碰撞測試次數不是2N次而是只有2N/2次。這一結論被應用到破解cryptographic hash function的生日攻擊中。生日問題所隱含的理論已經在[Schnabel 1938]名字叫做capture-recapture的統計試驗得到應用,來估計湖裡魚的數量。

相關評論

同義詞:暫無同義詞