誕生日のパラドックスのソースを表示

'''誕生日のパラドックス'''（たんじょうびのパラドックス、{{Lang-en-short|birthday paradox}}）とは「何人集まれば、その中に[[誕生日]]が同一の2人（以上）がいる[[確率]]が、50%を超えるか?」という問題から生じる[[パラドックス]]である。[[鳩の巣原理]]より、366人（[[閏日]]も考えるなら367人）が集まれば確率は100%となるが、その5分の1に満たない70人でもこの確率は99.9%を超え、50%を超えるのに必要な人数はわずか23人である。

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

この理論の背景には {{en|Z.E. Schnabel}} によって記述された「湖にいる魚の総数の推定<ref>Z. E. Schnabel (1938) ''The Estimation of the Total Fish Population of a Lake'', American Mathematical Monthly '''45''', 348–352.</ref>」がある。これは、[[統計学]]では[[標識再捕獲法|標的再捕獲法]] ({{en|capture‐recapture}}法) として知られている。

== 誕生日問題 ==
[[Image:Birthday Paradox.svg|thumb|right|400px|ある集団に同じ誕生日のペアがいる確率。23人で確率が初めて0.5を超えるのがわかる]]
上記の確率を求める問題やその類似問題は、'''誕生日問題'''とよばれる。

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

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

まずは、''n''人の誕生日が全て異なる場合の確率 ''p''<sub>1</sub> を計算する。

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''<sub>2</sub> は、
:<math>p_2(n)=1-{\dfrac{_{365}P_n}{365^n}}</math>
となり、''n'' = 23 のとき、''p''<sub>2</sub> = 0.507… となる。

一方、先ほどの、''n''人の部屋に"あなた"が入ったときに、あなたと同じ誕生日の人がいる確率 ''p''<sub>3</sub> は、
:<math>p_3(n) = 1- \left( \frac{364}{365} \right)^n</math>
となる。''n'' = 23 ならば、''p''<sub>3</sub> = 0.0611… である。''n'' が 253 のときに初めて ''p''<sub>3</sub> が 0.5 以上となる。

== 誕生日攻撃 ==
{{Main|誕生日攻撃}}
この誕生日問題の考え方は、誕生日攻撃と呼ばれる[[暗号]]システムへの攻撃法に利用されている。

=== ハッシュ関数の衝突 ===
ハッシュ値がNビットの理想的な[[暗号学的ハッシュ関数]]があるとする。このとき、あるハッシュ値となるメッセージを探し出す[[原像攻撃]]が成功する試行回数の期待値は2<sup>N-1</sup>である。それと比べて、同一のハッシュ値となる2通の異なるメッセージを探し出す[[衝突 (計算機科学)|衝突]]攻撃（[[誕生日攻撃]]）が成功する試行回数の期待値は、誕生日のパラドックスによって2<sup>N/2</sup>でありずっと小さい。このことは、暗号学的ハッシュ関数の使用目的にてらしあわせて、必要なハッシュ値の大きさに注意しなければならないことを意味している。原像攻撃に対する耐性が「弱衝突耐性」、誕生日攻撃に対する耐性が「強衝突耐性」である。

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

== 脚注 ==
{{reflist}}

== 外部リンク ==
* [https://keisan.casio.jp/exec/system/1161228814 誕生日が一致する確率] - 高精度計算サイト（[[カシオ計算機]]）
*{{高校数学の美しい物語|996|同じ誕生日の二人組がいる確率について|}}
*{{MathWorld|title=Birthday Problem|urlname=BirthdayProblem}}
* [http://www.efgh.com/math/birthday.htm The Birthday Paradox accounting for leap year birthdays]

{{DEFAULTSORT:たんしようひのはらとつくす}}
[[Category:暗号技術]]
[[Category:確率問題]]
[[Category:数学の問題]]
[[Category:応用確率論]]
[[Category:確率論のパラドックス]]
[[Category:誕生日]]
[[Category:数学に関する記事]]