操作して学ぶ
誕生日のパラドックス／UUID衝突確率
「365人いないと同じ誕生日は出ない」と思いがちですが、実際にはたった23人集めれば50%を超える確率で同じ誕生日のペアが現れます。 これは空間の大きさN個に対して、衝突確率が50%を超えるのに必要な個数がNではなくおよそ√N程度で済むという、直感に反する性質のためです。 UUIDのような巨大な空間でも同じ式が成り立つことを、グラフと実際の乱数生成で確かめられます。
ここが分かる
- 衝突確率が50%を超えるのに必要な個数は、空間の大きさNではなく約1.18×√Nで近似できる。365日なら約23人、100万通りの認証コードなら約1,177個。
- UUID v4（122ビットのランダム部）では約2.7×1018個集めて初めて50%に達する。「UUIDはほぼ絶対に衝突しない」という直感は、この桁の大きさが裏付けている。
- それでも同じ数式が支配している以上、生成する空間が狭い（4桁PINなど）と、思ったより少ない試行回数で衝突しうる。