こんにちは、鎌田です。
これは、TECHSCORE Advent Calendar 2016 の11日目の記事です。
はじめに
Advent Calendarといえば、クリスマス。
クリスマスといえば、イエス・キリストの誕生日！(´∀`pq)ﾊﾟﾁﾊﾟﾁ
ということで、今回のテーマは「誕生日のパラドックス」です。
ちなみに「誕生日のパラドックス」は衝突攻撃（誕生日攻撃）という攻撃手法の考え方のもとになっています。
衝突攻撃とは、ある関数 f に対しての f(a) ＝ f(b) となるような、同じ結果を返す a と b を求めるものです。
結果的には総当たり攻撃をすることになるのですが、どのくらいの攻撃回数で求める結果が得られるのか。を考えるときに非常に有効な手法です。
この「誕生日のパラドックス」が本当に正しいのか？という検証の結果を記事にしようと思います。
誕生日のパラドックスとは？
簡単に誕生日のパラドックスについて説明します。
誕生日のパラドックスとは「〇人の人が集まれば、誕生日が同じ人が存在する確率が50%を超えるか」という問題に対して、この〇が何人かを考えるものです。
直感的に考えると、1年は365日なので(うるう年の時は366日)、180人くらい...少なくとも50 ~ 60人くらいは必要そうな気がしますよね。
でも実際は、【23人】集まるだけでいいんです。
本当に？
さっそく検証
ここからRubyを使って、以下のA. ~ E.のような過程で検証してみます。
A.1人分の誕生日相当の数字を、乱数を"rand"を使って生成する。
|
1 2 |
> puts rand(365) 86 |
B.A.を"times"で23回繰り返し、"map"で配列としてまとめて、23人分の誕生日を生成する。
|
1 2 3 4 5 6 7 |
> puts 23.times.map{rand(365)} 100 207 83 ⋮ > puts 23.times.map{rand(365)}.size # 生成した乱数の数をカウント 23 |
C.23人の中に誕生日が同じ人がいるかを検出するために、"uniq"で重複を省く。
|
1 2 3 4 5 6 7 |
> puts 23.times.map{rand(365)}.uniq 139 88 243 ⋮ > puts 23.times.map{rand(365)}.uniq.size 22 # 22だったら誕生日が同じ人がいる |
D.重複を省いた結果が23より少なければ、23人の中に誕生日が同じ人がいることになり、trueが出力される。
|
1 2 3 4 |
> puts 23.times.map{rand(365)}.uniq.size < 23 true # 誕生日が同じ人がいる > puts 23.times.map{rand(365)}.uniq.size < 23 false # 誕生日が同じ人がいない |
E.A. ~ D.の過程を10,000回ほどループさせ、"select"でtrueを出力した数をとる。
5,000回以上重複していれば、50%の確率で誕生日が重複した人がいることになる。
|
1 2 |
> puts 10000.times.select{ 23.times.map{rand(365)}.uniq.size < 23 }.size 5150 |
検証結果
22人のときと23人のときで、5回ずつループさせて検証してみました。
- 22人のとき
|
1 2 3 4 5 6 |
> 5.times{puts 10000.times.select{ 22.times.map{rand(365)}.uniq.size < 22 }.size} 4810 4743 4721 4706 4717 |
22人だと5,000回近くにはなりますが、少し届かないですね...。
だいたい、47%くらいでしょうか。
- 23人のとき
|
1 2 3 4 5 6 |
> 5.times{puts 10000.times.select{ 23.times.map{rand(365)}.uniq.size < 23 }.size} 5023 5149 5062 5081 5143 |
23人にすると5,000回を超えてきました！
たしかに○人のなかに誕生日が同じ人がいる確率は、23人を境にして50%以上になるようです！
余談...
ちなみに70人以上いれば99.9%の確率で誕生日が衝突するペアがいるそうです！
気になった方は、ぜひ試してみてください。
