バースデーパラドックス(birthday paradox)っていうのがある。
人が集まった時に誕生日(月日の部分）が同じ人がいる確率はどんなもんかってやつ。
20人くらい集まると意外にも「40%」くらい。
23人になると、「50%」くらいになる。
結構確率高くない？
直観的な感覚と反するのでバースデーパラドックスっていうみたい。
母数がnの場合に、1.18×√nになると50%超えるらしい。
誕生日だと1年365日として1.18×√365(19.1)≒22.53なので23人くらいで
同じ誕生日の人が1組はいるって確率は50%って感じ。
※「自分と」同じ誕生日の人がいる確率じゃなくて集団の中で同じ誕生日の組が存在する確率。
で、実際にやってみた。以下Pythonで書いたコード。
365日で決まった試行回数ランダムに数値を引いて、かぶったのがあったかどうかを
10000回やってみて、どのくらいの割合かを見た感じ。
それを試行回数19、22、23回でそれぞれ5回ずつ。
import random
def challenge(limit):
tmp = []
for i in range(limit):
x = random.randint(1, 365)
if(x in tmp):
return True
tmp.append(x)
return False
def birthday(n):
ret = []
for i in range(10000):
if(challenge(n)):
ret.append(1)
else:
ret.append(0)
return ret
if __name__ == "__main__":
print("n=19")
for i in range(5):
ret = birthday(19)
print(f"{ret.count(1)} / {len(ret)} = {ret.count(1) / len(ret)}")
print("n=22")
for i in range(5):
ret = birthday(22)
print(f"{ret.count(1)} / {len(ret)} = {ret.count(1) / len(ret)}")
print("n=23")
for i in range(5):
ret = birthday(23)
print(f"{ret.count(1)} / {len(ret)} = {ret.count(1) / len(ret)}")
結果
n=19 3814 / 10000 = 0.3814 3693 / 10000 = 0.3693 3807 / 10000 = 0.3807 3785 / 10000 = 0.3785 3724 / 10000 = 0.3724 n=22 4846 / 10000 = 0.4846 4734 / 10000 = 0.4734 4752 / 10000 = 0.4752 4708 / 10000 = 0.4708 4759 / 10000 = 0.4759 n=23 5047 / 10000 = 0.5047 5058 / 10000 = 0.5058 5092 / 10000 = 0.5092 5007 / 10000 = 0.5007 5079 / 10000 = 0.5079
おお、確かにそんな感じになってる。。。
365程度だと、23回試行すると一回くらいは重複する可能性が50%あると。
100000くらいでも、373回試行で、1回くらい重複する可能性が50%。
割とかぶる可能性高いよね。
そう考えると、小学校のクラスって自分の時は３０～４０人くらいだったんですが、
割と同じ誕生日の人がいてもよさそうな感じがする。
1学年6クラスくらいあったとしたら6年生までで36組。
同じ誕生日の子がクラスにいるクラスが18クラスくらいあってもおかしくないわけで。
そういえば、高校の時、自分と1日違いの子が2人いたなー。
あれって別に珍しい事でも何でもなかったんですね。。。
ランダムな値で重複しなさそうーと思ってても、かぶる事って結構あるよね。
色々作ってたり使ってたりする中で、確かにそんな状況に出会う事はあったような気がする。
確率的な数値って、直観と反する事ってありますよね。
例えば、ドロップ率1000分の1の場合で、
実際に1000回倒して最低でも一つ出る確率は約63%だったり。
結構出ない。。。
↑の話って数式で考えると
(1 - 1/n)のn乗じゃないですか。
この形って↓じゃん。
↑のnが大きくなればなるほど、「0.36」辺りに収束すると。
↑のeってネイピア数っていうんですが、
だから、確率関連の数式には良く出てくるのかーって
意味も分からず納得してた記憶がある。
だから何だって話なんですが。
2020/7/19追記
そういえばUUIDはどうなんでしょ。
良く使ってるのはv4だと思うので、
wiki見てみると「2^122すなわち5.3×10^36」通りだけど、総数はこの半分になるらしい。
「2.6×10^36」くらいってことかしら？
wikiの誕生日攻撃のページの表だとドンピシャのものはないけど、128bitあたりのが近そう？
50%になるのは2^122*1/2らしいので2^61って事かしら。
でも50%だと高すぎるよね。。。
ハードディスクのエラー訂正不可能な確率が10^-18～10^15らしいので、wikiの表で128bit周りで見るとだいたい8200億回くらいまでは同一システム内で使ってるIDがかぶる事はあまり考慮しなくても良いって事なのかしら。
