アルゴリズムと計算量の問題

難易度 4大学院入試の標準レベル証明問題大学数学アルゴリズムと計算量

$p$ を素数、 $r$ を正の整数とし、 $F_{p} = {0, 1, \dots, p - 1}$ を $p$ を法とする剰余体とする。キーの集合を $U = F_{p}^{r}$ とし、 $a = (a_{1}, \dots, a_{r}) \in F_{p}^{r}$ に対してハッシュ関数 $h_{a} : U \to F_{p}$ を
$h_{a} (x) = a_{1} x_{1} + a_{2} x_{2} + \dots + a_{r} x_{r} (F_{p} での計算)$
で定める。ただし $x = (x_{1}, \dots, x_{r})$ である。

$n$ 個の相異なるキーからなる集合 $S \subseteq U$ を固定し、 $a$ を $F_{p}^{r}$ の $p^{r}$ 個の元から一様ランダムに選ぶ。各 $j \in F_{p}$ について、バケット $j$ に入るキーの個数を
$N_{j} = ∣ {x \in S : h_{a} (x) = j} ∣$
とおく。このとき
$E j \in F_{p} \sum N_{j}^{2} = n + \frac{n ( n - 1 )}{p}$
が成り立つことを証明せよ。

この問題で使うもの

ハッシュの衝突の期待値（説明と入口の問題）
指示変数と期待値の線形性（説明と入口の問題）

この問題を解けるようになるまで（71 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$\sum_{j} N_{j}^{2}$ を「同じバケットに入るキーの順序対の個数」と読みかえ、指示確率変数の和にして期待値の線形性を使いましょう。

ヒント 2

相異なる 2 キー $x, y$ について、 $h_{a} (x) = h_{a} (y)$ は $\sum a_{i} (x_{i} - y_{i}) = 0$ と同値です。 $x_{k} \neq = y_{k}$ となる成分 $k$ に注目し、 $F_{p}$ が体であることを使います。

ヒント 3

$\sum_{j} N_{j}^{2} = \sum_{x, y \in S} I_{x y}$ と書け、 $x = y$ の項から $n$ が出ます。残りは $n (n - 1)$ 個の順序対の衝突確率の和なので、1 対あたりの衝突確率を求めれば終わりです。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$\sum_{j} N_{j}^{2}$ を、 $S$ のキーの順序対 $(x, y)$ で衝突するものの個数（指示関数の和）に正しく書き換えている（3 点）
$x = y$ の対から $n$ が出ることと、相異なる順序対が $n (n - 1)$ 個あることを示し、期待値の線形性で衝突確率の和に帰着している（2 点）
衝突の条件を $\sum a_{i} (x_{i} - y_{i}) = 0$ と線形な条件に直し、 $x_{k} \neq = y_{k}$ となる成分 $k$ をとっている（2 点）
$F_{p}$ が体であることから $a_{k}$ が他の成分で一意に決まることを示し、衝突確率がちょうど $\frac{1}{p}$ であることを導いている（2 点）
以上をまとめて $n + \frac{n ( n - 1 )}{p}$ を結論している（1 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

証明は 2 段階で行う。まず $\sum_{j} N_{j}^{2}$ をキーの対ごとの衝突の指示関数の和に書き直し、次に相異なる 2 キーが衝突する確率がちょうど $\frac{1}{p}$ であることを示す。

ステップ 1：和の書き換え. $x, y \in S$ に対し、 $h_{a} (x) = h_{a} (y)$ のとき 1、そうでないとき 0 をとる確率変数を $I_{x y}$ とする。各 $j$ について
$N_{j}^{2} = (x \in S \sum [h_{a} (x) = j])^{2} = x \in S \sum y \in S \sum [h_{a} (x) = j] [h_{a} (y) = j]$
である（ $[P]$ は条件 $P$ が成り立てば 1、そうでなければ 0）。 $j$ について和をとると、各対 $(x, y)$ について $[h_{a} (x) = j] [h_{a} (y) = j]$ が 1 になる $j$ は、 $h_{a} (x) = h_{a} (y)$ のときちょうど 1 つ（ $j = h_{a} (x)$ ）、そうでないとき 0 個なので
$j \in F_{p} \sum N_{j}^{2} = x \in S \sum y \in S \sum I_{x y} = n + (x, y) \in S^{2}, x \neq = y \sum I_{x y}$
となる。ここで $x = y$ の $n$ 個の対では常に $I_{x x} = 1$ であることを用いた。期待値の線形性より
$E [j \sum N_{j}^{2}] = n + x \neq = y \sum P (h_{a} (x) = h_{a} (y)) (1)$
である。和は $S$ の相異なる 2 元の順序対全体にわたり、その個数は $n (n - 1)$ である。

ステップ 2：衝突確率. $x \neq = y$ を $S$ の 2 元とし、 $d = x - y = (d_{1}, \dots, d_{r})$ とおく。 $x \neq = y$ より $d_{k} \neq = 0$ となる添字 $k$ が存在する。 $h_{a}$ は $F_{p}$ 上で線形なので
$h_{a} (x) = h_{a} (y) ⟺ i = 1 \sum r a_{i} d_{i} = 0 ⟺ a_{k} d_{k} = - i \neq = k \sum a_{i} d_{i} .$
$p$ は素数なので $F_{p}$ は体であり、 $d_{k} \neq = 0$ には逆元 $d_{k}^{- 1}$ が存在する。よって上の条件は
$a_{k} = - d_{k}^{- 1} i \neq = k \sum a_{i} d_{i}$
と同値である。したがって、 $a_{k}$ 以外の成分 $(a_{i})_{i \neq = k}$ を任意に決めたとき（ $p^{r - 1}$ 通り）、条件を満たす $a_{k}$ はちょうど 1 つ存在する。よって条件を満たす $a \in F_{p}^{r}$ はちょうど $p^{r - 1}$ 個であり、 $a$ は $p^{r}$ 個から一様に選ばれるので
$P (h_{a} (x) = h_{a} (y)) = \frac{p ^{r - 1}}{p ^{r}} = \frac{1}{p} .$

結論. これを $(1)$ に代入すると、 $n (n - 1)$ 個の順序対それぞれが $\frac{1}{p}$ を寄与するので
$E j \in F_{p} \sum N_{j}^{2} = n + \frac{n ( n - 1 )}{p}$
が成り立つ。 $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる