17.4 誕生日則

教室に学生が \(95\) 人いる。同じ誕生日の学生がいる確率はどれくらいだろうか？ \(95\) と \(365\) を比べて、答えは \(1/4\) 程度だろうと思ったかもしれない ── それは間違いである: \(95\) 人の学生の中に同じ誕生日の二人が含まれる確率は \(0.999\) を超える。

これを示すために、学生が特定の誕生日を持つ確率は常に \(1/d\) であり、ランダムに選ばれた独立な学生が \(n\) 人いると仮定する。先ほどの例では \(d = 365\) および \(n = 95\) だったものの、以降の議論では一般的な結果を考えるとしよう。なお、このランダム性の仮定は現実には正しくない: 新生児は一年を通して全く同じペースで産まれるわけではないし、学生による講義の選択は他の学生の選択の影響を受ける。ただ、こうした単純化によって問題の解析が始められるようになる。さらに重要なこととして、この誕生日一致問題の情報科学における重要な応用では上述の仮定が正当化される場合が多い。例えば、ハッシュテーブルにランダムな要素をいくつか挿入するときに発生する衝突は誕生日一致問題としてモデル化すると上手く議論できる。よって「\(4\) 月に生殖が増えるので \(1\) 月の出産が多い」や「双子は同じ講義を受ける傾向にある」といった (正しいかどうかも分からない) 噂はこれから無視する。

17.4.1 誕生日が一致する確率を表す厳密な式

この仮定の下で、\(n\) 人の学生の誕生日を並べた列は \(d^{n}\) 通り存在し、それらの確率は全て等しい。また、異なる誕生日を並べた長さ \(n\) の列は \(d(d - 1)(d - 2) \cdots (d - (n - 1))\) 通り存在する。よって全員の誕生日が異なる確率は次のように表せる:

\[ \begin{align*} & \frac{d(d - 1)(d - 2) \cdots (d - (n - 1))}{d^{n}} \\[10pt] & \qquad = \frac{d}{d} \cdot \frac{d - 1}{d} \cdot \frac{d - 2}{d} \cdots \frac{d - (n - 1)}{d} \tag{17.4} \\[13pt] & \qquad = \left( 1 - \frac{0}{d} \right) \left( 1 - \frac{1}{d} \right) \left( 1 - \frac{2}{d} \right) \cdots \left( 1 - \frac{n - 1}{d} \right) \tag{17.5} \end{align*} \]

続いて、不等式 \(1 - x < e^{-x}\) (\(x > 0\)) を使って式 \(\text{(17.5)}\) を変形する。この不等式は Taylor 級数 \(e^{-x} = 1 - x + x^{2}/2! - x^{3}/3 + \cdots\) から分かる。

\[ \begin{align*} & \left( 1 - \frac{0}{d} \right) \left( 1 - \frac{1}{d} \right) \left( 1 - \frac{2}{d} \right) \cdots \left( 1 - \frac{n - 1}{d} \right) \\[12pt] & \qquad < e^{0} \cdot e^{-1/d} \cdot e^{-2/d} \cdot \cdot e^{-(n-1)/d} \tag{17.6} \\[5pt] & \qquad = e^{-\sum_{i=0}^{n-1} i/d} \\[5pt] & \qquad = e^{-n(n - 1)/2d} \tag{17.7} \end{align*} \]

式 \(\text{(17.7)}\) に \(n = 95\) と \(d = 365\) を代入すると、\(n\) 人の学生全員の誕生日が異なる確率は \(1/200{,}000\) 未満だと分かる。言い換えれば、誕生日が一致する学生がいる確率は \(1 - 1/200{,}000 > 0.99999\) を超える。そのため、もし教室に同じ誕生日の学生がいなかったら、それは驚異的な現象である。

\(d \leq n^{2}/2\) なら、誕生日が一致する学生が存在しない確率は上界 \(\text{(17.7)}\) に漸近等価となる。特に \(d = n^{2} / 2\) なら、その確率は \(1/e\) に漸近等価となる。ここから情報科学の様々な文脈で有用となる事実が得られる:

誕生日則 (birthday principle)

一年が \(d\) 日で、部屋に \(\sqrt{2d}\) 人がいるなら、その部屋に同じ誕生日の二人がいる確率は約 \(1 - 1/e \approx 0.632\) である。

例えば、誕生日則からは \(\sqrt{2 \cdot 365} = 27\) 人が部屋にいるとき同じ誕生日の二人がいる確率が約 \(0.632\) だと分かる。実際の値は \(0.626\) なので、近似は非常に正確な値を与える。

誕生日則の応用の一つとして、次の事実がある: ハッシュテーブルなどで \(n\) 個の要素を \(d\) 個の領域にハッシュ関数で割り当てるとき、\(n^{2}\) が \(d\) と同程度に大きいと衝突が発生する可能性が高い。また、誕生日則は暗号システムに対する誕生日攻撃 (birthday attack) に関係することでも有名である。