生日悖論

悖論內容

著名的生日悖論

23個人里有兩個生日相同的人的幾率有多大呢？

居然有50%

問題是這樣的：如果一個房間裡有23個或23個以上的人，那么至少有兩個人的生日相同的機率要大於50%。這就意味著在一個典型的標準國小班級(30人)中，存在兩人生日相同的可能性更高。對於60或者更多的人，這種機率要大於99%。

不計特殊的年月，如閏二月。

先計算房間裡所有人的生日都不相同的機率，那么

第一個人的生日是 365選365

第二個人的生日是 365選364

第三個人的生日是 365選363

:

第n個人的生日是 365選365-(n-1)

所以所有人生日都不相同的機率是：

那么，n個人中有至少兩個人生日相同的機率就是：

所以當n=23的時候，機率為0.507

當n=100的時候，機率為0.999999692751072

對於已經確定的個人，生日不同的機率會發生變化。下面用隨機變數計算：

令X[i,j]表示第i個人和第j個人生日不同的機率，則易知任意X[i,j]=364/365

令事件A表示n個人的生日都不相同

P(A)=

解P(A)<1/2，由對數可得：n>=23

相比之下，隨機變數也同樣的簡單易懂

，且計算起來要方便得多

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

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

生日悖論普遍的套用於檢測哈希函式:N-位長度的哈希表可能發生碰撞測試次數不是2^N次而是只有2^(N/2)次。這一結論被套用到破解cryptographic hash function的生日攻擊中。

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