ハッシュの衝突確率（誕生日問題）

出力が $N$ 通りのランダムなハッシュで $k$ 個の値がすべて異なる確率 $\prod_{i = 0}^{k - 1} (1 - \frac{i}{N})$ を求め、余事象で衝突確率を求められる。近似 $1 - e^{- k (k - 1) / (2 N)}$ を使って衝突確率が $\frac{1}{2}$ を超える $k$ のおよその大きさ（ $\approx N$ の定数倍）を見積もれる

前提

確率の定義と和事象・余事象（数学A 場合の数と確率）
テイラー展開（大学数学微分積分）

この技能までの道筋（57 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
関数の連続性と中間値の定理（数学III 極限）
平均値の定理（数学III 微分法）
積と商の微分（数学III 微分法）
第 2 次導関数とグラフの凹凸（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
増減・凹凸・漸近線とグラフ（数学III 微分法）
テイラー展開（大学数学微分積分）

説明

出力が $N$ 通りのハッシュ関数に $k$ 個の異なる入力を与えたとき、出力のどこかが一致する（衝突する）確率を求める技能です。「40 人のクラスに同じ誕生日の 2 人がいる確率」と同じ構造なので、誕生日問題とも呼ばれます。まず全部が異なる確率を正確に求め、余事象で衝突確率を出します。さらに指数関数による近似を使うと、衝突確率が $\frac{1}{2}$ を超えるのは $k$ がおよそ $1.18 N$ に達したときだとわかります。これは、ハッシュ値の長さが安全性に十分かどうかを見積もるときに使います。

なぜそうしてよいのか

モデルを決めます。各入力のハッシュ値は $N$ 通りのどれかに等確率でなり、入力ごとに独立に決まるとします。 $k$ 個の出力の並びは重複順列で $N^{k}$ 通りあり、どれも同様に確からしい根元事象です。すべて異なる並びは $N$ 個から $k$ 個を並べる順列で $N (N - 1) \dots (N - k + 1)$ 通りあります。よって
$P (すべて異なる) = \frac{N ( N - 1 ) \dots ( N - k + 1 )}{N ^{k}} = i = 0 \prod k - 1 (1 - \frac{i}{N}) .$
$i$ 番目（ $i = 0, 1, \dots$ ）の値が、それまでに出た $i$ 個の値のどれとも違う確率が $1 - \frac{i}{N}$ だと考えても同じ式になります。「少なくとも 1 組が衝突する」は「すべて異なる」の余事象なので、衝突確率は $1 - \prod_{i = 0}^{k - 1} (1 - \frac{i}{N})$ です。なお $k > N$ のときは因子 $1 - \frac{N}{N} = 0$ が含まれるので、衝突確率は $1$ になります（鳩の巣原理）。

近似のために、 $e^{- x}$ のテイラー展開を剰余項つきで書きます。ある $θ$ （ $0 < θ < 1$ ）を用いて $e^{- x} = 1 - x + \frac{e ^{- θ x}}{2} x^{2}$ と表せ、剰余項は $0$ 以上です。したがって、すべての実数 $x$ で $1 - x \leq e^{- x}$ が成り立ちます。 $x$ が小さいときは $x^{2}$ の項が無視できるので、 $1 - x \approx e^{- x}$ となります。 $0 \leq \frac{i}{N} < 1$ のとき各因子は正なので、これらを掛け合わせると
$i = 0 \prod k - 1 (1 - \frac{i}{N}) \leq exp (- i = 0 \sum k - 1 \frac{i}{N}) = e^{- k (k - 1) / (2 N)}$
が得られます。ここで $\sum_{i = 0}^{k - 1} i = \frac{k ( k - 1 )}{2}$ （等差数列の和）を使いました。よって衝突確率は $1 - e^{- k (k - 1) / (2 N)}$ 以上で、 $k$ が $N$ に比べて十分小さいとき両者はほぼ等しくなります。

近似式で衝突確率が $\frac{1}{2}$ 以上になる条件は $e^{- k (k - 1) / (2 N)} \leq \frac{1}{2}$ です。両辺の対数をとると $k (k - 1) \geq 2 N lo g 2$ となります。 $k$ が大きいとき $k (k - 1) \approx k^{2}$ なので、 $k \approx 2 lo g 2 N \approx 1.18 N$ です。ペアの個数 $(2 k) = \frac{k ( k - 1 )}{2}$ が $k$ の 2 乗に比例して増えるので、 $N$ に比べてずっと少ない $N$ 程度の個数で衝突が起こりやすくなります。

手順

出力の総数 $N$ と値の個数 $k$ を確認する。 $k > N$ なら衝突確率は $1$ で終わり。
すべて異なる確率を積で書く: $P = i = 0 \prod k - 1 (1 - \frac{i}{N}) = \frac{N ( N - 1 ) \dots ( N - k + 1 )}{N ^{k}}$
余事象で衝突確率を出す: $1 - P$
見積もりだけが必要なら近似を使う: $1 - P \approx 1 - e^{- k (k - 1) / (2 N)}$ （正確な値はこれ以上になる）
衝突確率 $\frac{1}{2}$ の目安を求めるときは $k (k - 1) \geq 2 N lo g 2$ を解く。おおよそ $k \approx 1.18 N$ となる。

例題

出力が $8$ 通りのランダムなハッシュ関数に、異なる $4$ 個の入力を与える。各出力は $8$ 通りに等確率かつ独立に決まるとする。少なくとも 1 組のハッシュ値が一致する確率を求めよ。

例題の解答

手順 1: $N = 8$ , $k = 4$ であり、 $k \leq N$ を満たす。

手順 2: すべて異なる確率は
$P = (1 - \frac{0}{8}) (1 - \frac{1}{8}) (1 - \frac{2}{8}) (1 - \frac{3}{8}) = \frac{8 \cdot 7 \cdot 6 \cdot 5}{8 ^{4}} = \frac{1680}{4096} = \frac{105}{256}$
である。

手順 3: 余事象をとると、衝突確率は $1 - \frac{105}{256} = \frac{151}{256} \approx 0.590$ となる。

（参考・手順 4: 近似式では $1 - e^{- 4 \cdot 3/16} = 1 - e^{- 0.75} \approx 0.528$ となる。これは正確な値 $0.590$ 以下であり、不等式と合っている。 $k / N$ が大きいので近似の誤差も大きめになっている。）

答え: $\frac{151}{256}$

よくある誤り

衝突確率を $\frac{k}{N}$ や $\frac{k ( k - 1 )}{2 N}$ としてしまう誤り。正しくは $1 - \prod_{i = 0}^{k - 1} (1 - \frac{i}{N})$ である。 $\frac{k ( k - 1 )}{2 N}$ は衝突確率の上からの目安にすぎず、 $1$ を超えることもある（例: $N = 8, k = 4$ で $0.75$ 。正確な値は $\frac{151}{256}$ ）。
積の範囲を $i = 1$ から $k$ までとしてしまう誤り。1 個目はどの値でも衝突しないので因子は $1 - \frac{0}{N}$ である。正しくは $\prod_{i = 0}^{k - 1} (1 - \frac{i}{N})$ で、分子は $N (N - 1) \dots (N - k + 1)$ と $k$ 個の積になる。
「特定の 1 個と同じ値が出る確率」 $1 - (1 - \frac{1}{N})^{k - 1}$ と混同する誤り。正しくは、誕生日問題は「どこかの 2 個が一致する」確率であり、ペアが $(2 k)$ 組あるので、はるかに少ない $k \approx 1.18 N$ で $\frac{1}{2}$ を超える。
衝突確率が $\frac{1}{2}$ になるのは $k \approx \frac{N}{2}$ だと考える誤り。正しくは $k (k - 1) \approx 2 N lo g 2$ より $k \approx 2 lo g 2 N$ である。例えば $N = 365$ なら $k \approx 23$ で、 $183$ ではない。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

ハッシュの衝突の期待値（大学数学アルゴリズムと計算量）