確率・統計と待ち行列
10個のキーを、100個のバケットを持つハッシュ表に入れる。各キーは、それぞれ独立に、100個のバケットのどれかに等しい確率で割り当てられるとする。2つのキーの組のうち、同じバケットに割り当てられる組の数の期待値はどれか。
- A0.1
- B0.45
- C0.9
答えと解説を見る
正解：B. 0.45
10個のキーから2つを選ぶ組は 10C2 = 45組あり、それぞれの組が同じバケットに入る確率は1/100です。期待値の線形性(和の期待値は期待値の和)により、同じバケットに入る組の数の期待値は 45 × 1/100 = 0.45 です。期待値の線形性は組どうしが独立でなくても成り立つので、組ごとの確率を足すだけで求められます。
- A. キーの数10を100で割った値で、キーの組の数を数えていません。
- B. 正しい。10C2 ÷ 100 = 45 ÷ 100 = 0.45 です。
- C. 10 × 9 = 90 は順番を区別した組の数で、同じ組を2回ずつ数えています。