「誕生日のパラドックス」を検証してみた。


こんにちは、鎌田です。
これは、TECHSCORE Advent Calendar 2016 の11日目の記事です。

はじめに

Advent Calendarといえば、クリスマス。
クリスマスといえば、イエス・キリストの誕生日!(´∀`pq)パチパチ

ということで、今回のテーマは「誕生日のパラドックス」です。
ちなみに「誕生日のパラドックス」は衝突攻撃(誕生日攻撃)という攻撃手法の考え方のもとになっています。
衝突攻撃とは、ある関数 f に対しての f(a) = f(b) となるような、同じ結果を返す a と b を求めるものです。
結果的には総当たり攻撃をすることになるのですが、どのくらいの攻撃回数で求める結果が得られるのか。を考えるときに非常に有効な手法です。
この「誕生日のパラドックス」が本当に正しいのか?という検証の結果を記事にしようと思います。

誕生日のパラドックスとは?

簡単に誕生日のパラドックスについて説明します。

誕生日のパラドックスとは「〇人の人が集まれば、誕生日が同じ人が存在する確率が50%を超えるか」という問題に対して、この〇が何人かを考えるものです。
直感的に考えると、1年は365日なので(うるう年の時は366日)、180人くらい...少なくとも50 ~ 60人くらいは必要そうな気がしますよね。

でも実際は、【23人】集まるだけでいいんです。
%e7%84%a1%e9%a1%8c%ef%bc%92
本当に?

さっそく検証

ここからRubyを使って、以下のA. ~ E.のような過程で検証してみます。

A.1人分の誕生日相当の数字を、乱数を"rand"を使って生成する。

B.A.を"times"で23回繰り返し、"map"で配列としてまとめて、23人分の誕生日を生成する。

C.23人の中に誕生日が同じ人がいるかを検出するために、"uniq"で重複を省く。

D.重複を省いた結果が23より少なければ、23人の中に誕生日が同じ人がいることになり、trueが出力される。

E.A. ~ D.の過程を10,000回ほどループさせ、"select"でtrueを出力した数をとる。
5,000回以上重複していれば、50%の確率で誕生日が重複した人がいることになる。

検証結果

22人のときと23人のときで、5回ずつループさせて検証してみました。

  • 22人のとき

22人だと5,000回近くにはなりますが、少し届かないですね...。
だいたい、47%くらいでしょうか。

  • 23人のとき

23人にすると5,000回を超えてきました!
たしかに○人のなかに誕生日が同じ人がいる確率は、23人を境にして50%以上になるようです!

余談...

ちなみに70人以上いれば99.9%の確率で誕生日が衝突するペアがいるそうです!

気になった方は、ぜひ試してみてください。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です