ハッシュの衝突の期待値

一様ハッシュのチェイン法で、衝突する組の個数・キーを 2 個以上含むバケットの個数・最初の衝突までの挿入回数 $E [T] = \sum_{t \geq 0} P (T > t)$ などの期待値を求められる

前提

指示変数と期待値の線形性（大学数学アルゴリズムと計算量）
条件付き確率と乗法定理（数学A 場合の数と確率）
独立な試行と反復試行（数学A 場合の数と確率）
ハッシュの衝突確率（誕生日問題）（大学数学暗号理論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
期待値（数学A 場合の数と確率）
確率変数と確率分布（数学B 統計的な推測）
平均と合計（算数いろいろな文章題）
平均値・中央値・最頻値（中学数学データの活用）
代表値（平均値・中央値・最頻値）（数学I データの分析）
分散と標準偏差（数学I データの分析）
変量の変換と平均・分散（数学I データの分析）
確率変数の期待値・分散と $a X + b$ （数学B 統計的な推測）
確率変数の和と積（独立な場合）（数学B 統計的な推測）
指示変数と期待値の線形性（大学数学アルゴリズムと計算量）
条件付き確率と乗法定理（数学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$ 個のキーを $m$ 個のバケットに一様に入れたときの「衝突する組の個数」「キーを 2 個以上含むバケットの個数」「最初の衝突が起こるまでの挿入回数」の期待値を、指示変数と期待値の線形性を使って求めます。表の大きさ $m$ をどう決めるかなど、ハッシュ表の性能を見積もる場面で使います。

なぜそうしてよいのか

一様ハッシュのモデルでは、各キーは $m$ 個のバケットのどれかに確率 $\frac{1}{m}$ ずつで入り、キーごとの行き先は互いに独立だとします。数えたい量を「小さな事象が起きたら 1、起きなければ 0」という指示変数の和に分けます。期待値の線形性は独立性を必要としないので、各事象の確率を足すだけで期待値が求まります。たとえば相異なるキー $i < j$ の組ごとに「同じバケットに入る」という事象を考えます。 $j$ の行き先が $i$ の行き先と一致する確率は $\frac{1}{m}$ です。組は $_{n} C_{2}$ 個あるので、衝突する組の個数の期待値は $\frac{_{n} C _{2}}{m} = \frac{n ( n - 1 )}{2 m}$ です。バケット $b$ ごとに「キーを 2 個以上含む」という事象を考えると、反復試行の確率から $P = 1 - (1 - \frac{1}{m})^{n} - n \cdot \frac{1}{m} (1 - \frac{1}{m})^{n - 1}$ が得られます。これを $m$ 倍したものが、キーを 2 個以上含むバケットの個数の期待値です。

最初の衝突までの挿入回数 $T$ は、「何番目に入れたキーが、すでにキーのあるバケットに初めて入ったか」を表します。 $T$ は正の整数値をとり、鳩の巣原理から $T \leq m + 1$ です。正の整数 $T$ は、 $t = 0, 1, 2, \dots$ のうち $T > t$ をみたすもの（ $t = 0, 1, \dots, T - 1$ の $T$ 個）を数えた値に等しくなります。つまり $T = \sum_{t \geq 0} I (T > t)$ と指示変数の和で書けます。線形性から $E [T] = \sum_{t \geq 0} P (T > t)$ です。

事象「 $T > t$ 」は「最初の $t$ 個のキーがすべて異なるバケットに入る」ことと同じです。乗法定理で順に掛ければ $P (T > t) = \prod_{i = 0}^{t - 1} (1 - \frac{i}{m})$ となり、これは誕生日問題の「すべて異なる確率」そのものです。 $t = 0, 1$ では $1$ 、 $t \geq m + 1$ では $0$ になります。

手順

モデルを確認する：キー $n$ 個、バケット $m$ 個で、各キーは独立に確率 $\frac{1}{m}$ ずつで各バケットに入る。
数えたい量を指示変数の和に分ける。衝突する組なら組 ${i, j}$ ごと、2 個以上含むバケットならバケットごとに指示変数を置く。最初の衝突時刻なら $T = \sum_{t \geq 0} I (T > t)$ と書く。
各事象の確率を求める。組が衝突する確率は $\frac{1}{m}$ 、バケットが 2 個以上含む確率は $1 - (1 - \frac{1}{m})^{n} - \frac{n}{m} (1 - \frac{1}{m})^{n - 1}$ 、 $P (T > t) = \prod_{i = 0}^{t - 1} (1 - \frac{i}{m})$ である（ $P (T > 0) = P (T > 1) = 1$ ）。
期待値の線形性で確率を足し合わせる。たとえば $E [T] = \sum_{t = 0}^{m} P (T > t)$ と計算する（ $t \geq m + 1$ の項は $0$ ）。

例題

バケットが $m = 4$ 個のチェイン法のハッシュ表に、キーを 1 個ずつ挿入する。各キーは独立に確率 $\frac{1}{4}$ ずつでどれかのバケットに入るとする。すでにキーのあるバケットに初めてキーが入ったときの挿入回数（何個目のキーか）を $T$ とする。 $E [T]$ を求めよ。

例題の解答

手順 1：キーは独立に確率 $\frac{1}{4}$ ずつで各バケットに入る。バケットは 4 個なので、鳩の巣原理より $T \leq 5$ である。

手順 2： $T$ は正の整数なので $T = \sum_{t \geq 0} I (T > t)$ と書ける。よって $E [T] = \sum_{t \geq 0} P (T > t)$ である。

手順 3： $T > t$ は「最初の $t$ 個がすべて異なるバケットに入る」ことである。乗法定理より、各項は次のとおり。
- $P (T > 0) = 1$
- $P (T > 1) = 1$
- $P (T > 2) = \frac{3}{4}$
- $P (T > 3) = \frac{3}{4} \cdot \frac{2}{4} = \frac{3}{8}$
- $P (T > 4) = \frac{3}{8} \cdot \frac{1}{4} = \frac{3}{32}$
- $t \geq 5$ では $P (T > t) = 0$

手順 4：足し合わせる。
$E [T] = 1 + 1 + \frac{3}{4} + \frac{3}{8} + \frac{3}{32} = 2 + \frac{24 + 12 + 3}{32} = \frac{103}{32} .$

（検算）分布を直接求めると次のとおり。
- $P (T = 2) = \frac{1}{4}$
- $P (T = 3) = \frac{3}{4} \cdot \frac{2}{4} = \frac{3}{8}$
- $P (T = 4) = \frac{3}{8} \cdot \frac{3}{4} = \frac{9}{32}$
- $P (T = 5) = \frac{3}{32}$

よって $E [T] = \frac{16 + 36 + 36 + 15}{32} = \frac{103}{32}$ となり、一致する。

答え: $\frac{103}{32}$

よくある誤り

$E [T] = \sum_{t \geq 1} P (T \geq t)$ と $\sum_{t \geq 0} P (T > t)$ を混同して、 $\sum_{t \geq 1} P (T > t)$ のように項を 1 つ落とす誤り。上の例では $E [T]$ が $1$ 小さい $\frac{71}{32}$ になってしまう。正しくは $E [T] = \sum_{t \geq 0} P (T > t)$ で、 $t = 0$ の項 $1$ も含める。
「バケットがキーを 2 個以上含む確率」を $1 - (1 - \frac{1}{m})^{n}$ としてしまう誤り。これは「1 個以上含む」確率である。正しくは、ちょうど 1 個の場合も引いて $1 - (1 - \frac{1}{m})^{n} - \frac{n}{m} (1 - \frac{1}{m})^{n - 1}$ とする。
衝突する組の個数と、衝突に関わるキーの個数を混同する誤り。3 個のキーが同じバケットに入ると、衝突する組は $_{3} C_{2} = 3$ 組ある。組の個数の期待値は $\frac{n ( n - 1 )}{2 m}$ で、 $\frac{n}{m}$ ではない。
各バケットの指示変数が独立でないので、線形性が使えないと考えてしまう誤り。期待値の線形性は独立性を必要としないので、 $E [\sum_{b} I_{b}] = \sum_{b} P (A_{b})$ はそのまま成り立つ。

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

ハッシュの衝突の期待値

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題