23 人の見知らぬ人に尋ねると、そのうち二人の誕生日が同じである確率は 0.50729723432399 です。計算機は 1 − permutations(365,23)/365²³ としてそこに至り、分子は 23 人の誕生日がすべて異なる場合の数です。半分をほんのわずかに超えるだけなので、この結果は今なおパラドックスに読めます。57 人なら 0.99 を超えます。
直感に反するのは、比較ではなく人数を数えてしまうからです。23 人は combinations(23,2) = 253 組のペアを作り、それぞれ約 1/365 の機会が 253 回あることが半分の線を越えさせるのであって、23 という数ではありません。同じ算術が、ハッシュの衝突が表の大きさから想像するよりはるかに早く来る理由でもあります。問題が始まるのは空間の平方根のあたりで、だからこそ 128 ビットのハッシュは約 64 ビットの衝突耐性を持つとみなされます。
答え
0.50729723432399
読み方
計算機での 1 − permutations(365,23)/365²³。二つ目のリンクは補事象の 0.49270276567601 を与えます。どちらも浮動小数点値なので、末尾の桁は算術ではなく丸めです。
出典
The birthday problem, popularised by Richard von Mises in 1939; the 365-day uniform model ignores leap days and the real seasonality of births
電卓で解いてみる
これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。