誕生日のパラドックス

誕生日のパラドックス（たんじょうびのパラドックス）とは「何人集まればその中に同じ誕生日の人がいる確率が50%を超えるか?」という問題から生じるパラドックスである。鳩の巣原理より、366人（閏日も考えるなら367人）集まれば確率は100%となるが、しかしその5分の1に満たない70人が集まれば確率は99.9%を超え、50%を超えるのに必要なのはわずか23人である。

誕生日のパラドックスは論理的な矛盾に基づいているという意味でのパラドックスではなく、結果が一般的な直感と反しているという意味でのパラドックスである。

この理論の背景には テンプレート:En によって記述された「湖にいる魚の総数の推定」がある。これは、統計学では テンプレート:En 法として知られている。

誕生日問題

ファイル:Birthday Paradox.svg

ある集団に同じ誕生日のペアがいる確率。23人で確率が0.5になっているのがわかる

上記の確率を求める問題やその類似問題は、誕生日問題とよばれる。

部屋に22人の人間がいる。あなたがその部屋に入ったときに、「あなたと同じ」誕生日の人がいる確率は50％ではない。その確率はずっと低い。これは、「あなた以外の人」同士の誕生日が同じであるという可能性は考慮されないからである。

それでは、n人の中で同じ誕生日の人が少なくとも2人いる場合の確率を計算する。閏年や双子は考えないものとし、誕生日は365日とも等確率であるとする。

まずは、n人の誕生日が全て異なる場合の確率 p₁ を計算する。

2人目が1人目と異なっている誕生日である確率は、364/365 である。次に、3人目が1人目2人目と異なる誕生日である確率は 363/365 である。同様に4人目は 362/365、…、n人目は (365-n+1)/365 となる。 つまり、n人の誕生日が全て異なる確率は次のようになる。

<math>p_1 (n) = \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人いる場合の確率 p₂ は、

<math>p_2(n) = 1 - { 365! \over 365^n (365-n)! }</math>

となり、n = 23 のとき、p₂ = 0.507… となる。

一方、先ほどの、n人の部屋に"あなた"が入ったときに、あなたと同じ誕生日の人がいる確率 p₃ は、

<math>p_3(n) = 1- \left( \frac{364}{365} \right)^n</math>

となる。n = 23 ならば、p₃ = 0.0611… である。n が 253 のときに初めて p₃ が 0.5 以上となる。

誕生日攻撃

テンプレート:Main この誕生日問題の考え方は、誕生日攻撃と呼ばれる暗号解読法に利用されている。

ハッシュ関数の衝突

ハッシュ関数の出力の長さが、Nビットであるときには、2^N/2ではなく、2^N/2程度の文字列を試すことで同じハッシュ値を持つ文字列を見つけ出せる可能性が高い。 これは、ハッシュ関数の出力はある程度の長さを持つ必要があることを示している。

CTRモードの乱数識別性

ブロック暗号アルゴリズムをCTRモードで使用した擬似乱数生成器は、ブロック長をLとしたときに、2^L/2程度のブロック分の乱数出力を行うと1/2の確率で真の乱数と区別できる。真の乱数は誕生日のパラドックスから、2^L/2ブロック分の乱数の中に同じ値を持つブロックが約1/2の確率で存在する。一方でCTRモードはカウンタが同じ値に戻らないことから同じ値を持つブロックは存在しない。

外部リンク

• 誕生日が一致する確率 - 高精度計算サイト（カシオ計算機）テンプレート:Link GA

Z. E. Schnabel (1938) The Estimation of the Total Fish Population of a Lake, American Mathematical Monthly 45, 348–352.