誕生日のパラドックス
誕生日のパラドックス（たんじょうびのパラドックス）とは「何人集まればその中に同じ誕生日の人がいる確率が50％を超えるか?」という問題から生じるパラドックスであり、答えは23人である。直感的な答えよりもずっと少なくはないだろうか。 誕生日のパラドックスは論理的な矛盾に基づいているという意味でのパラドックスではなく、結果が一般的な直感と反しているという意味である。
この理論の背景にはZE Schnabelによって記述された「湖にいる魚の総数の推定（"The estimation of the total fish population of a lake."）」がある。これは、統計学ではcapture-recapture法として知られている。
誕生日問題
上記の確率を求める問題やその類似問題は、誕生日問題とよばれる。
部屋に22人の人間がいる。あなたがその部屋に入ったときに、「あなたと同じ」誕生日の人がいる確率は50％ではない。その確率はずっと低い。これは、「あなた以外の人」の誕生日が同じであるという可能性は考慮されないからである。
それでは、n人の中で同じ誕生日の人が少なくとも2人いる場合の確率を計算する。閏年や双子は考えないものとし、誕生日は365日とも等確率であるとする。
まずは、n人の誕生日が全て異なる場合の確率を計算する。
2人目が1人目と異なっている誕生日である確率は、364/365である。次に、3人目が1人目2人目と異なる誕生日である確率は363/365である。同様に4人目は362/365、…、n人目は(365-n+1)/365となる。 つまり、n人の誕生日が全て異なる確率は次のようになる。
- <math>p = \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdot \cdots \cdot \frac{365-n+1}{365} = { 365! \over 365^n (365-n)! }</math>
よって、n人の中で同じ誕生日の人が少なくとも2人いる場合の確率は、:
- <math>p = 1 - { 365! \over 365^n (365-n)! }</math>
となり、nが23のとき、p=0.507...となる。
一方、先ほどの、n人の部屋に"あなた"が入ったときに、あなたと同じ誕生日の人がいる確率は、
- <math> 1- \left( \frac{364}{365} \right)^n </math>
となる。n=23 ならば、p = 0.0611...である。nが253のときに初めてpが0.5以上となる。
この誕生日問題の考え方は、誕生日攻撃と呼ばれる暗号解読法に利用されている。 ハッシュ関数の出力の長さが、Nビットであるときには、2Nではなく、2N/2程度の文字列を試すことで同じハッシュ値を持つ文字列を見つけ出せる可能性が高い。 これは、ハッシュ関数の出力はある程度の長さを持つ必要があることを示している。
