内部ハッシュ法

m(m-1)・・・(m-i+1)/B(B-1)・・・(B-i+1)≒(m/B)^i
となぜ書けるのですか？
だんだん値がだんだん小さくなっていくから
こうなる　では、あんまり良くなくて、もう少し
ちゃんとしたものを・・・ということなんです・・・。
わかる方がいらっしゃったら教えてください。

No.2 ベストアンサー 回答者： siegmund 回答日時： 2001/11/29 11:26

内部ハッシュ法はよく知りませんが，

式の方だけ分析してみましょう．

stomachman さんのおっしゃるとおりなのですが，
もう少し突っ込んでみましょう．
問題の式をから (m/B)^i という因子を引っ張り出すと
(1)　　m(m-1)・・・(m-i+1)/B(B-1)・・・(B-i+1) = (m/B)^i {f(m,i)/f(B,i)}
の形になります．
(2)　　f(n,i) = 1 (1-1/n) (1-2/n) ・・・ {1-(i-1)/n}
問題の近似式は {f(m,i)/f(B,i)}≒１ としているわけです．
B,m >> i なら近似がよいのは直感的に明らかですが，
近似の程度を見てみましょう．
(2)を展開して，最低次の項までとると
(3)　　f(n,i) ≒ 1 - Σ(j=1～i-1) (j/n) ≒ 1 - i(i-1)/ 2n
ですから
(4)　　f(m,i)/f(B,i) ≒ 1 + i(i-1)/2 {1/B - 1/m}
で近似の程度が明確になりました．
ん，B=m だと最低次の補正項が消えるのか？
そりゃそうです．
B=m なら
(5)　　m(m-1)・・・(m-i+1)/B(B-1)・・・(B-i+1) = 1 = (m/B)^i
で，近似が正確な値を与えますから．

この回答へのお礼

詳しく教えていただき、ありがとうございましたm(_ _)m
順序があって、大変わかりやすかったです。
「なるほど・・・」と感動しました。
これからちゃんと理解しているか確認のためも含めて、
レポートを書いてみようと思います。

お礼日時：2001/11/29 16:10

No.1 回答者： stomachman 回答日時： 2001/11/29 04:29

m=8, i=8, B=9としてみれば左辺=0.11, 右辺=0.39。

あんまり似てませんねえ。

この近似は、
m, Bがiに比べてうんと大きいときだけ有効なんですよ。

m/B≒(m-1)/(B-1)≒…(m-i+1)/(B-i+1)
と近似して、
だから左辺≒(m/B)^i
とやっただけのことです。

この回答へのお礼

なるほど！！
わかりやすく教えていただき、ありがとうございましたm(_ _)m
これでレポートもなんとかできそうです。

お礼日時：2001/11/29 16:07