本稿は機械翻訳であり、原文は英語です。 原文を読む
23人と、予期すべき偶然の一致
23人からは253組のペアができる。誰もその253という数を計算しようとしないこと、それこそが答えが直感に反して感じられるすべての理由である。
部屋に23人を集めると、そのうちの2人が誕生日を共有する確率は50.7%である。70人の場合は99.9%になる。
ほぼすべての人がはるかに大きすぎる人数を推測するが、その理由は間違った問いを立てているからである。直感的には自分自身について考えてしまい、「ここにいる誰かが私の誕生日と同じである確率はどのくらいか？」と問いかけてしまう。それははるかに稀な事象であり、その確率が半分を超えるには約253人が必要となる。
実際の問いは、任意のペアに関するものである。そして、ペアは決して乏しくない。
人数ではなく、ペアを数える
23人からは 23 × 22 ÷ 2 = 253 組の異なるペアができる。それぞれのペアが一致する確率は365分の1である。ペアの数は人数の2乗に応じて増加するため、部屋の人数を2倍にすると、偶然の一致の機会は4倍になる。
正確な計算は逆の手順で行う。すなわち、どの2人も一致しない確率を求めるのである。これは 365/365 × 364/365 × 363/365 × … と23項にわたって計算することになり、0.493となる。1からそれを引いた値が0.507である。
覚えておく価値のある一般的な法則
等しい確率で起こる N 通りの可能性がある場合、重複が発生する確率が半分を超えるまでには、およそ √N 回の抽出が必要となる。誕生日であれば √365 ≈ 19 であり、定数を考慮すると約 1.18 × √N ≈ 22.5 となる。23にきわめて近い数値である。
半分ではなく、平方根である。これこそが人々が誤解している数値であり、偶然の一致を実際よりも稀なものと思い込む原因となっている。
単なる余興にとどまらない領域
ハッシュ衝突。 1000個のスロットを持つハッシュテーブルは、エントリ数が1000近くに達したときに衝突し始めるわけではない。衝突は約30個の時点で発生し始める。これが、ハッシュテーブルの実装において最初の挿入時から衝突処理に配慮する理由であり、負荷係数だけを測定しても検索に要するプローブ回数についてほとんど分からない理由である。Hash Table ツールは、予想よりもはるかに早く衝突が発生することを示している。
暗号技術。 ここでは平方根がセキュリティパラメータを決定する。同じ64ビットのハッシュ値を持つ2つの異なる文書を見つけるのに、2⁶⁴回の試行は必要ない。必要なのは約2³²回（およそ40億回）であり、これはわずか数分の作業に過ぎない。これが誕生日攻撃であり、n ビットの衝突耐性を提供することを意図したハッシュ関数が 2n ビットの出力を生成しなければならない理由である。128ビットのハッシュが64ビットの衝突耐性しか提供しないとみなされ、署名用途においてもはや受け入れられない理由もここにある。
偶然の一致の解釈。 十分に大きなデータセットには著しい偶然の一致が必ず含まれており、その数はレコード数ではなくペアの数に応じて拡大する。同じ街の2人が宝くじに当選する、1つの通りで特定の病気が集中的に発症する、2つの曲が似て聞こえる——これらは規模が拡大すればほぼ確実なものとなり、それぞれを個別に起こりそうにないこととして扱うのは、人と誕生日に関してなされるのと同じ計算上の誤りである。
正しい問いは、決して「この特定の偶然の一致はどれほど起こりにくいか？」ではない。「この種の何らかの偶然の一致が起こる機会はどれほど存在したか？」である。これら2つの数値の差は2次関数的に増大する倍率によって開いていき、驚きを予期へと変えるには十分すぎるほどである。
答える価値のある2つの異論
「誕生日は一様ではない。」 実際に一様ではない。北半球では夏の終わりに誕生が多く、12月25日や2月29日には少なく、計画分べんのために週末には明らかな減少が見られる。しかし、非一様性は常に一致の確率をより高めるものであり、低くすることはない。集中によって、実質的により少ない日数に人々が偏るからである。したがって、一様であるという前提は控えめな試算であり、23人はどちらかといえばわずかに過大評価である。
「双子や、一緒におとずれた人々。」 実際の部屋は無作為な標本ではない。兄弟姉妹がいる部屋や、年齢の区切りによって分けられた児童のクラスには、モデルに含まれていない相関関係が存在する。この計算は独立な抽出を前提とした基準であり、抽出が独立でない場合に検証されるべきなのは独立性の前提であって、計算そのものではない。
常に覚えておきたい簡易版
等しい確率である N 個のカテゴリがあり、k 回の抽出を行う場合、衝突するペアの数の期待値はおよそ k²/2N である。これを1とおくと k ≈ √(2N) が得られる。これは確率ではなく期待される衝突数を数えることで到達する同じ平方根であり、暗算で行うのもより容易である。
1000個のハッシュスロットの場合、√2000 ≈ 45 となるため、最初の衝突は40代の件数あたりで期待される。32ビットのチェックサムの場合、2¹⁶ = 65,536 個の項目となり、これはログファイルが半日で達する量である。365日の場合、27となり、23に十分近いため、この推測は信頼するに値する。
「重複が起こる確率はどのくらいか」と聞かれたら、常に平方根を用いる習慣を身につけ、空間の広さが示唆するよりもずっと早く答えが届くことに留意されたい。Birthday Paradox ツールはこの曲線をグラフ化しており、20人から30人あたりで見せる急激な立ち上がりは言葉の説明だけでは捉えきれない部分である。