この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

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

難易度 1教科書の例題レベル大学数学アルゴリズムと計算量

バケット数 $3$ のチェイン法ハッシュ表が最初は空である。この表に、互いに異なる $4$ 個のキーを挿入する。各キーのハッシュ値は $3$ 個のバケットのどれかに等確率 $\frac{1}{3}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。 $4$ 個のキーをすべて挿入し終えたとき、キーを $2$ 個以上含むバケットの個数の期待値を求めよ。

この問題で使うもの

ハッシュの衝突の期待値（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

「ハッシュの衝突の期待値」の技能を使う。数えたい量をバケットごとの指示変数の和 $X = I_{1} + I_{2} + I_{3}$ に分け、期待値の線形性で $E [X] = \sum P (A_{i})$ とする。

ヒント 2

1 つのバケットに入るキーの個数は、確率 $\frac{1}{3}$ の反復試行 $4$ 回で決まる。「 $2$ 個以上」は余事象「 $0$ 個または $1$ 個」を使うと計算しやすい。

ヒント 3

バケット $1$ のキーが $0$ 個または $1$ 個である確率は $(\frac{2}{3})^{4} + 4 \cdot \frac{1}{3} \cdot (\frac{2}{3})^{3} = \frac{16}{27}$ 。あとは $1$ から引いて $3$ 倍する。

答えと解説

答えを見る

\frac{11}{9}

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

解説を読む

方針：数えたい量「キーを $2$ 個以上含むバケットの個数」を、バケットごとの指示変数の和に分けて、期待値の線形性を使う。

手順 1（指示変数に分ける）　バケットに $1, 2, 3$ と番号をつけ、 $i = 1, 2, 3$ に対して
$I_{i} = {10 (バケット i にキーが 2 個以上入る) (それ以外)$
とおく。求める個数は $X = I_{1} + I_{2} + I_{3}$ であり、期待値の線形性（独立でなくても成り立つ）から
$E [X] = E [I_{1}] + E [I_{2}] + E [I_{3}] = P (A_{1}) + P (A_{2}) + P (A_{3})$
である。ただし $A_{i}$ は「バケット $i$ にキーが $2$ 個以上入る」という事象。

手順 2（1 つのバケットについて確率を求める）　バケット $1$ に注目する。各キーがバケット $1$ に入るかどうかは、確率 $\frac{1}{3}$ で「入る」独立な試行の $4$ 回の繰り返し（反復試行）である。余事象「キーが $0$ 個または $1$ 個」の確率は
$(\frac{2}{3})^{4} +_{4} C_{1} \cdot \frac{1}{3} \cdot (\frac{2}{3})^{3} = \frac{16}{81} + \frac{32}{81} = \frac{48}{81} = \frac{16}{27} .$
よって
$P (A_{1}) = 1 - \frac{16}{27} = \frac{11}{27} .$
対称性から $P (A_{2}) = P (A_{3}) = \frac{11}{27}$ である。

手順 3（足し合わせる）
$E [X] = 3 \cdot \frac{11}{27} = \frac{11}{9} .$

（確認） $3^{4} = 81$ 通りの入り方を、各バケットのキー数の型で分けると、 $(4, 0, 0)$ が $3$ 通り、 $(3, 1, 0)$ 型が $24$ 通り、 $(2, 2, 0)$ 型が $18$ 通り、 $(2, 1, 1)$ 型が $36$ 通り。 $2$ 個以上を含むバケット数はそれぞれ $1, 1, 2, 1$ なので、合計は $3 + 24 + 36 + 36 = 99$ 、期待値は $\frac{99}{81} = \frac{11}{9}$ となり一致する。

答え： $\frac{11}{9}$

別解

バケット $i$ ( $i = 1, 2, 3$ ) に入るキーの個数を $X_{i}$ とすると、 $X_{i} \sim Bin (4, 1/3)$ である。

$P (X_{i} = 0) = (2/3)^{4} = 16/81$
$P (X_{i} = 1) = 4 \cdot \frac{1}{3} \cdot (2/3)^{3} = 32/81$

よって $P (X_{i} \geq 2) = 1 - \frac{16 + 32}{81} = \frac{33}{81} = \frac{11}{27}$ 。

求める個数は $\sum_{i} 1 [X_{i} \geq 2]$ なので、期待値の線形性より $3 \cdot \frac{11}{27} = \frac{11}{9}$ 。

検算として、 $81$ 通りのハッシュ値の割り当てを分類する。
- 個数が $(4, 0, 0)$ 型: $3$ 通りで、 $2$ 個以上のバケットは $1$ 個。
- $(3, 1, 0)$ 型: $24$ 通りで、 $2$ 個以上のバケットは $1$ 個。
- $(2, 2, 0)$ 型: $18$ 通りで、 $2$ 個以上のバケットは $2$ 個。
- $(2, 1, 1)$ 型: $36$ 通りで、 $2$ 個以上のバケットは $1$ 個。

合計は $3 + 24 + 36 + 36 = 99$ なので、期待値は $99/81 = 11/9$ となり一致する。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題