バースデイパラドックス

「あるクラスに30人の生徒がいます。この中に、誕生日が一致する組が1組以上あると思いますか?」

あなたはそのクラスの人の誕生日を誰一人分も知らないとして、この賭けは「ある」方が有利か「ない」方が有利か、という問題。

感覚としては無さそうに思えるが、実は「ある」確率が約70%と高い(クラスの人数が23人で確率が1/2を超える)。

これと同じく、ある関数にランダムな値を入れたとき、出てくる値がk種類あるとするなら(先の例ならk=365である)、1.2×k^(1/2)回の試行で同じ値を得る確率が約1/2となることが知られており、この現象をバースデイパラドックス(Birthday paradox)と言う。

またこれを元にした攻撃手法は誕生日攻撃(Birthday attack)と呼ばれている。