お誕生日はおいくつですか。ハッシュ衝突の背後にある数学についてです。

【注】本稿はこれまでの投稿とはやや異なっております。対話形式ではなく、より論文調の記述に近づけています。何度も構成を検討しましたが、題材自体が直線的には収まらず、ある種の「形」を持っていることに気づき、そのままで残しました。ご覧ください！

あなたが周囲の人々と同じ誕生日を持つ確率はどれほどでしょうか？もしあなたがお一人で部屋にいるなら、それはもちろんゼロです。さらに言えば、人が集まるにつれて、その確率は高くなるはずです。しかし、「23 人しかいない部屋であっても、二人が同じ誕生日を持つ確率が既に 50% に達している」と言われたら、どう感じるでしょう？実はこれを中学校レベルの数学で容易に証明できます。

「少なくとも二人の人が同じ誕生日を持つ確率」を計算するとはなんでしょうか。それは、「グループ内で誰も同じ日生まれではない」という事象の逆確率を求めることと等価です：

[ P(\text{少なくとも一人一致}) = 1 - P(\text{誰とも不一致}) ]

「不一致」とは、つまりすべての誕生日が一意であることを意味します。すなわち、一人目は何れの日も生まれうる（365 日のうちどれでもよい）、二人目は異なる日であるために 364 日しか選べない、三人目はさらに 363 日しか選べない……という具合に続きます。そこで、部屋にいる人数を $n$ とし、この式を導出してみましょう：

[ P(\text{誰とも不一致}) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365-n+1}{365} = \frac{365!}{365^n(365-n)!} ]

ここで $n=23$ とおくと：

[ P(\text{誰とも不一致}) = \frac{365!}{365^{23}(365-23)!} \approx 0.4927 ]

つまり、約 50% です。

インターネットで「Birthday Paradox（誕生日のパラドックス）」を検索するとよく見られるもう一つの式は、23 人の間のすべての組み合わせが存在する確率を算出した近似式です：

[ 1 - \frac{1}{365} = \frac{364}{365} ] [ P = \left( \frac{364}{365} \right)^{\binom{23}{2}} \approx 0.4995 ]

しかし、さらに面白いものを見てみましょう。

前述の式の問題点は、一致するペアを見つけることにしか使えない点です。では、「60 人中に 3 人が同じ誕生日を持つことはどれくらいレアな事象なのでしょうか？」という問いには、これらの式は答えられません。

1930 年代のある保険会社の数学部門のエリートたちは、自社の 60 人の同僚の中に、3 人が同じ誕生日を持っている件を発見しました。彼らはその確率を計算しようとしたのだと考えられます。計算の流れはおそらく以下のようなものでした：

「60 人の部屋で、Alice、Bob、Ray の三人が同じ誕生日を持つ場合の確率は、それぞれ $\frac{1}{365}$ の積なので、 [ \left(\frac{1}{365}\right)^3 ] です。残りの 57 人の同僚については、この特定の日以外に生まれる確率を考慮すると、 [ \left(\frac{364}{365}\right)^{57} ] となります。」

さらに、Alice・Bob・Ray という三人組ではなく、Mikel・Ida・Ana または他のどの三人組であってもよいことから、組み合わせの数を： [ \binom{60}{3} ] として考慮します。これらすべての確率を掛け合わせると：

[ \binom{60}{3} \cdot \left(\frac{364}{365}\right)^{57} \cdot \left(\frac{1}{365}\right)^3 \approx 0.0006 ]

となります。つまり、数学部門の職人が得た結果は、わずか万分の一程度にすぎません。そして、彼らの計算自体は正確でした。しかし同時に……間違っていました。

その理由を説明したのは、1939 年にイギリス出身の数学者 Richard von Mises（リヒャルト・フォン・マイゼス）です。彼の論文「Über Aufteilungs- und Besetzungswahrscheinlichkeiten（分配および占有確率について）」は、ナチスの支配から逃れ、イスラエル出身という理由でユダヤ人として分類されながらも、伊スタンブールの大学の学術誌に掲載されました。その後彼は数学の教授を務めることになりました。

フォン・マイゼスは単に計算式を変更しただけではありません。問題の視座そのものを変えました。人間の大脳は自己中心的であり、よく全体像を見失ってしまうのです。数学部門の職員らは、「特定の出来事」、すなわち「三人が選んだ特定の日（事前に選ばれた日）に誕生日を持つ確率」を求めようとしていました。しかし、逆に尋ねてみましょう：「このような類いの出来事が一般的にはどの頻度で起こるでしょうか？」という問い方ではありませんか？

想像してみてください。あなたの前に 365 個の箱があります。そこへランダムに 60 個のボールが投げ入れられます。数学部門の職員らは、特定の箱（第三番目の箱）を選び、「その箱の中に 3 個以上のボールが入っていること」を成功と定義します。一方、フォン・マイゼスは「すべての箱を観察し、最終的に 3 個以上ボールが入った箱がいくつあるかを数えるべき」と提案しました。明らかなのは、彼の定義する「成功」の条件ははるかに広く、そのせいで得られる確率もはるかに大きくなるということです。

フォン・マイゼスは、このような確率を「占有確率（occupancy probability）」と呼びました。これは、箱（ここでは日付）がそれぞれ 1 回、2 回、3 回……のように占められている数を表すものです。

彼の計算式を見てみましょう。ここでは $n$ を日数の数え上げ、$k$ を部屋にいる人数とします。

各日 $n$ が少なくとも一つ占められる確率は $\frac{1}{n}$ であり、$k$ 人の全員について考えると：

[ \underbrace{\frac{1}{n} \times \frac{1}{n} \times \cdots \times \frac{1}{n}}_{k\text{ 回}} = \frac{1}{n^k} = n^{-k} ]

これは、ある特定の一連の順序が起こる確率を表します。

次に、最初の暦日（カレンダー上の一日）にちょうど $s$ 人の誕生日が集中する分布に対する確率 $p_1$ を構築します。$k$ 人中から $s$ 人を選び出す方法は $\binom{k}{s}$ 通りあり、残りの $n-1$ 日のうち $(k-s)$ 名の従業員をどのように分配するかですが：

[ (n-1)^{k-s} ]

となります。したがって、$p_1$ の完全な式は：

[ p_1 = \binom{k}{s} \cdot n^{-k} \cdot (n-1)^{k-s} ]

この $p_1$ をベルヌーイ試行（Bernoulli trials）の観点から書き換えることもできます：

$$ \begin{aligned} p_1 &= \binom{k}{s} \cdot (n-1)^{k-s} \cdot n^{-k} \ &= \binom{k}{s} \cdot \frac{(n-1)^{k-s}}{n^k} \ &= \binom{k}{s} \cdot \frac{(n-1)^{k-s}}{n^s \cdot n^{k-s}} \ &= \binom{k}{s} \cdot \left(\frac{1}{n}\right)^s \cdot \left(\frac{n-1}{n}\right)^{k-s} \ &= \binom{k}{s} \cdot \left(\frac{1}{n}\right)^s \cdot \left(1 - \frac{1}{n}\right)^{k-s} \end{aligned} $$

ここで、 $$p = \frac{1}{n} \quad \text{（成功の確率）}$$ $$q = 1 - \frac{1}{n} \quad \text{（失敗の確率）}$$

と置くと、高校で習ったベルヌーイ数列の公式が得られます。

同様の式は $p_2, p_3, \dots, p_n$ にも適用でき、以下のように求まります：

[ p_1 + p_2 + p_3 + \cdots + p_n = n \cdot p_1 ]

この総和は、「少なくとも一日に $s$ 人の誕生日が集中するすべての分配」をカバーします。また、より多くの異なる日に同じ数（例えば二日以上）で $s$ 人がいる場合、その分布は重複してカウントされます（例：2 日目にそれぞれ $s$ 人ずついる場合、その分布は 2 回カウントされる）。

これは、各日の誕生日の数を表す多数のアレイ（配列）を持つような状況を想像すると分かりやすいです（本例では 4 日のみ考慮します）：

$s = 7$ の場合： 分配結果（各日の人数）： $$ \begin{aligned} \text{Distribution}_1 &: [8, \mathbf{7}, 4, 6] \ \text{Distribution}_2 &: [4, 5, 3, 2] \ \text{Distribution}_3 &: [\mathbf{7}, 4, 5, \mathbf{7}] \end{aligned} $$

確認対象のアレイ（ちょうど $s$ 人の誕生日を持つ日を調べる）： $$ \begin{aligned} \text{Array}_1 &: [8, 4, \mathbf{7}] \quad \text{(日付 1)} \ \text{Array}_2 &: [\mathbf{7}, 5, 4] \quad \text{(日付 2)} \ \text{Array}_3 &: [4, 3, 5] \quad \text{(日付 3)} \ \text{Array}_4 &: [6, 2, \mathbf{7}] \quad \text{(日付 4)} \end{aligned} $$

Distribution1 は Array2 のみで現れるため、一度だけカウントされ、Distribution3 は Array1 および Array4 に同時に含まれるため、二度カウントされます。

つまり、$n \cdot p_1$ は加重総和を与え、「期待値 $E(x_s)$」と解釈できます。これには、さっき導出した $p_1$ の式をそのまま代入するだけでよい：

[ E(x_s) = n \cdot \binom{k}{s} \cdot (n-1)^{k-s} \cdot n^{-k} ]

あるいは

[ E(x_s) = n \cdot \binom{k}{s} \cdot \left(\frac{1}{n}\right)^s \cdot \left(1 - \frac{1}{n}\right)^{k-s} ]

60 人組に三人が同じ誕生日を持つことがもっとも一般的であることを証明するために、上記の式に数値を入れてみましょう：

$$ \begin{aligned} n &= 365 \ k &= 60 \ s &= 3 \ E(x_3) &= 365 \times \frac{60!}{3! \times (60-3)!} \times \left(\frac{1}{365}\right)^3 \times \left(1 - \frac{1}{365}\right)^{60-3} \approx 0.2196 \end{aligned} $$

すなわち約 0.22 となり、フォン・マイゼスが論文で示した値と一致します。

「0.22」はあまりに少ないように思えるかもしれませんが、実際には「平均して 4〜5 組の 60 人組あたり、一人に三人が同じ誕生日を持つケースがある」ということを意味しています。

[ \frac{1}{0.22} \approx 4.5454 ]

これではあまりレアではありませんよね？特に、これは千分の数値（つまり約 1,500〜2,000 組に一度しか現れない）とは対照的です。後者は本当にレアな出来事です。

もちろん、これらの計算は、出生の季節変動、双子の有無、サンプリングバイアス、閏年などを考慮していません。フォン・マイゼスの論文末尾でも彼はこれらについて明確に触れています。統計を見ると、北半球では夏に生まれた子供が多くなっていますし、米国ではクリスマスや新年前夜に受胎される傾向があります。さらに剖産や人工催産の影響で、月曜・火曜日の出生率も高くなるなどです。

フォン・マイゼスの論文では正確な確率分布の計算が続きますが、数学部門が問題の視点を間違えていたことを証明するには期待値だけで十分です。

また、期待値を用いることで、選択する値に応じてハッシュテーブル内で発生する衝突（コリジョン）数の近似表現も得られます。

さらに、サイバーセキュリティにおいて「Birthday Attack（誕生日攻撃）」と呼ばれる特殊なブルースフォース攻撃が存在します。この攻撃は、 Birthday Problem の数学的性質を利用して、システムを機能停止させるための衝突を意図的に作成します。攻撃者はランダムな入力を生成し続け、二つの入力が出すハッシュ値が一致するのを待ちます。その必要とされる試行回数は約 $\sqrt{n}$ です。例えば SHA-256 では出力空間が $2^{256}$ なので、これを突破するには $2^{128}$ 回の試行が必要です。なお、攻撃者は特定のハッシュ値が二重になるのを待つのではなく、単に何らかの衝突さえあればシステムは機能しないため、その時点で十分です。

私たちは以前にもハッシュテーブルにおける衝突について少し触れましたね。今回の話を通じて、ハッシュテーブルの衝突背後にある数学と Birthday Problem の背後にある数学は同一であることが分かりました：日付がテーブルのフィールドに置き換えられ、人々がハッシュ値に変換されますが、計算の本質部分は不変です。

参考資料およびさらに読むべき文献：

• Richard Von Mises、「Über Aufteilungs- und Besetzungswahrscheinlichkeiten」（p. 313）
• Richard von Mises の人物伝
• University of Connecticut の講義資料