書記が数学やるだけ#852 誕生日問題，クーポンコレクター問題

確率にまつわる問題として誕生日問題とクーポンコレクター問題を扱う。

問題

説明

誕生日問題とは「何人集まれば，その中に誕生日が同一の2人（以上）がいる確率が，50%を超えるか?」といった問題で，50%を超えるのに必要な人数は23人である。直感的には「自分の誕生日と一致する確率」で考えしまうがために必要人数を過大評価することから，誕生日のパラドックスとも呼ばれる。

これの応用が暗号システムに対する誕生日攻撃である。あるハッシュ関数がH個の値を出力し得る場合，平均で約1.25√H回の試行で同じハッシュ値を取る2つの値の組を発見できる。

クーポンコレクター問題とは，「全てのクーポンを集めると何らかの特典が得られる」場合に何回クーポンを引けばよいかという問題である。

解答

誕生日問題を考えるには，余事象としてn人全員の誕生日が異なる確率を求める。これは1人ずつ誕生日を調べるように分解することで求めることができる。

これを一般化したものが誕生日攻撃における衝突確率である。ここで，e^-xの近似を用いた。

クーポンコレクター問題の下準備として，いわゆる当たり確率1/nのガチャをn回引いた時に当たりが出る確率を求めておく。

クーポンコレクター問題についても1種ずつ当たりが出る時間で分解して考えると，これは幾何分布に従うことから期待値について線形性が成り立ち，全種類が出揃うまでの購入回数Nの期待値E(N)が求められる。

本記事のもくじはこちら：