# 誕生日原理 Navigation: [[index]] | [[overview]] ## 定義 誕生日原理(Birthday Principle)は、d 日の1年があり、d 日の中から独立にランダムに選ばれた人が部屋に √(2d) 人集まると、そのうち2人の誕生日が一致する確率がおよそ 1 − 1/e ≈ 0.632 になるという経験則である。 厳密には、n 人全員の誕生日が異なる確率は $ \prod_{i=0}^{n-1}\left(1 - \frac{i}{d}\right) < e^{-n(n-1)/2d} $ という上界を持つ(不等式 1 − x < e^{−x} を用いて導かれる)。d ≥ n²/2 の範囲ではこの上界は「誰も一致しない確率」の漸近的に正確な値になり、特に d = n²/2 のとき「誰も一致しない確率」は漸近的に 1/e に等しくなる。ここから、√(2d) 人集まれば一致確率がおよそ 1 − 1/e になるという原理が導かれる。95人のクラス(d=365)では、一致確率は0.9999を超える。 計算機科学への応用として、n 個の要素をサイズ d のハッシュ表に格納する際、n² が d の無視できない割合を超えると衝突が多発することの説明に使われるほか、暗号系を破る「誕生日攻撃(birthday attack)」の理論的基盤にもなる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 16 Events and Probability Spaces]] §16.4) ## 横断的知見 - 第18章のクーポン収集問題(coupon collector problem: n種類の景品を全種類集めるまでに必要な回数の期待値)は、本頁の誕生日原理と同じ「d通りの値からランダムに値を引き続ける」設定を扱うが、問う量が異なる。誕生日原理は「√(2d) 回引けば衝突(重複)がおよそ起こる」という**衝突までの回数**を組合せ論的な数え上げ(全員の誕生日が異なる確率の上界)で評価するのに対し、クーポン収集問題は「d通り全種類を集めるには何回必要か」という**網羅までの回数**を期待値の線形性で評価する(答えは d·Hd ≈ d·ln(d) 回、Hd は調和数)。同じ「ランダムな値の引き当て」という現象について、d²のオーダーで起こる事象(衝突)と d·ln(d) のオーダーで起こる事象(網羅)という、桁の異なる2つのしきい値が対比される。第18章は実際に「365人集めて全員の誕生日を網羅する期待人数は 365·H365 ≈ 2364.6人」という具体例で誕生日原理の題材を再利用している。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 16 Events and Probability Spaces]] §16.4, [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.5.4) ## 未解決の問い - 本章の誕生日原理はランダムかつ独立な誕生日という単純化の仮定に基づく(実際には誕生日は季節で偏り、クラス選択は独立でないことが本文でも明示されている)。ハッシュ関数の設計や暗号の誕生日攻撃を扱う別ソースが入ってきたとき、この単純化の仮定がどこまで正当化されるかを追記する必要がある。 - 誕生日攻撃を実際の暗号プロトコル(ハッシュ関数の衝突耐性など)に適用する具体例は本章では触れられていない。セキュリティ関連ソースの ingest 時に補強する。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 16 Events and Probability Spaces]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] - 概念: [[確率空間]](誕生日原理は一様確率空間上の数え上げの応用例)、[[四段階法]](誕生日原理の導出は四段階法とは異なる、組合せ論的な数え上げのアプローチを取る)、[[期待値]](クーポン収集問題は誕生日原理と同じ設定を期待値の線形性で評価する対の問題) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 16 §16.4; Chapter 18 §18.5.4.