ここ数年の話なのですが，何かを成し遂げたり，何かの節目だったりすると，
頑張った自分に対して，何かしらのご褒美を用意するようにしています。

今回は，半年間授業を頑張った自分へのご褒美として，
こんなものを買っちゃいました！

ヘルスメーターです！

むちゃくちゃ安かった上に，本体は B5 サイズと，その小柄なボディに惚れて即購入！

体脂肪を測ったりとか，高度な機能はまったくありませんが，
場所は取らないし，一番知りたい体重は教えてくれるし，
個人的にはなかなか気に入ってます！

とりあえず，目指すは現状維持！！（欲を言えば，2 kg 減）

————— ｷﾘﾄﾘｾﾝ 8X —————

ご褒美に浮かれてばかりじゃいられない，ってことで，
第 2 章の範囲で苦手な確率の問題を紹介ー！

[問題]
キー値の分布が 1 ～ 1,000,000 の範囲で一様にランダムであるデータ 5 個を，大きさ 10 のハッシュ表に登録する場合，衝突の起こる確率はおよそいくらか。ここで，ハッシュ値はキー値をハッシュ表の大きさで割った余りを用いる。

　(ア) 0.2　　　(イ) 0.5　　　(ウ) 0.7　　　(エ) 0.9

この問題は，まず，衝突の起こらない確率について考え，
そこから以下の式を元に，衝突の起こる確率を求めて，問題を解いていきます。

　　　　1 – 衝突の起こらない確率 = 衝突の起こる確率　…(a)

ちなみに，ハッシュ値を求める場合，
必ず，衝突が起こるか起こらないかのどちらかの場合になるため，

　　　衝突が起こる場合 + 衝突の起こらない場合 = すべての場合(= 1)

が成り立つことから，(a) の式を導くことができます。

なお，問題文の赤色の部分から，ハッシュ表のハッシュ値は，
キー値をハッシュ表の大きさ 10 で割った余りなので，

　　　キー値 / 10 の 余り = 0 ～ 9 の 10 個の値のいずれか

ということが分かります。

続いて，5 つのデータにおける，衝突の起こらない確率ですが，
これは，それぞれの場合についての可能性を順番に考えていけば OK です。

　・ 最初（1 つ目）のデータの場合
　　→ まだ，ハッシュ表にはデータが 1 つも格納されていないので，
　　　 最初のデータのハッシュ値は 0 ～ 9 のどの値でも構いません。
　　　 よって，衝突が起こらない可能性は 1（10 分 の10）となります。

　・ 2 つ目のデータの場合
　　→ ハッシュ表には，すでに 1 つのデータが格納されているので，
　　　 2 つ目のデータのハッシュ値は，最初のデータのハッシュ値以外の
　　　 9 個の値のうちのいずれか，でなければなりません。
　　　 つまり，衝突が起こらない可能性は 0.9（10 分の 9）となります。

　・ 3 つ目のデータの場合
　　→ 2 つ目のデータと同様に，すでに 2 つのデータがハッシュ表に格納されているので，
　　　 3 つ目のデータのハッシュ値は，8 個の値のうちのいずれか，になります。
　　　 したがって，衝突が起こらない可能性は 0.8（10 分の 8）です。

　・ 4 つ目のデータ，5 つ目のデータの場合
　　→ 2 つめ以降にならって，それぞれの衝突の起こらない可能性を考えると，
　　　 4 つ目のデータの場合は 0.7（10 分の 7），
　　　 5 つ目のデータの場合は 0.6（10 分の 6）となります。

以上の可能性は，同時には起こらないので，

　　　1 × 0.9 × 0.8 × 0.7 × 0.6 = 0.3024（衝突の起こらない確率）

となります。

これを (a) の式に当てはめると，1 – 0.3024 ≒ 0.7 となり，
正解は (ウ) であることが分かります。