生日悖論

生日悖論是指，如果一個房間裡有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%。