バースデイパラドックス
読み：バースデイパラドックス
外語：Birthday paradox
誕生日に関するパラドックス(逆説、奇説)の代表例。
概要
「あるクラスに30人の生徒がいます。この中に、誕生日が一致する組が1組以上あると思いますか?」
あなたはそのクラスの人の誕生日を誰一人分も知らないとして、この賭けは「ある」方が有利か「ない」方が有利か、という問題。
特徴
感覚としては無さそうに思えるが、実は「ある」確率が約70%と高い(クラスの人数が23人で確率が1/2を超える)。
これと同じく、ある関数にランダムな値を入れたとき、出てくる値がk種類あるとするなら(先の例ならk=365である)、1.2×k(1/2)回の試行で同じ値を得る確率が約1/2となることが知られており、この現象をバースデイパラドックス(Birthday paradox)と言う。
またこれを元にした攻撃手法は誕生日攻撃(Birthday attack)と呼ばれている。
再検索