2009年7月21日 星期二

生日悖論

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

對此悖論的解釋


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

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

應用

生日悖論普遍的應用於檢測哈希函數:N-位長度的哈希表可能發生碰撞測試次數不是2N次而是只有2N/2次。這一結論被應用到破解密碼學散列函數的生日攻擊中。

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

近似匹配

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

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

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

0 意見:

張貼留言