[http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83%A0%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF:title=ブルームフィルタ]


上記のリンク先の "誤検出の可能性" に書かれた数式
[tex:(1-(1-1/m)^{kn})^k \simeq (1-e^{-kn/m})^k]
の両辺がほぼ等しい理由を教えて下さい。

回答の条件
  • 1人3回まで
  • 登録:2007/12/04 18:27:45
  • 終了:2007/12/09 06:22:37

ベストアンサー

id:quintia No.1

quintia回答回数561ベストアンサー獲得回数702007/12/04 20:55:28

ポイント100pt

\lim_{n \to \infty} (1-\frac{1}{n})^n = e^{-1} から導くのだと思います。


質問の式の左辺の中にある(1-\frac{1}{m})^{kn}を、(1-\frac{1}{m})^{m\cdot \frac{kn}{m} と変形します。

ここで「mが十分に大きく(1-\frac{1}{m})^{m} の部分をe^{-1}で近似できる」とすると、e^{-1 \cdot \frac{kn}{m}}の形になり、右辺にあるe^{-kn/mがでてきます。


最初の式は指数関数の定義 e^x\equiv\lim_{n \to \infty} (1+\frac{x}{n})^nx=-1 を代入した形です。

id:koori

ありがとうございました。納得できました。

> ここで「mが十分に大きく(1-\frac{1}{m})^{m} の部分をe^{-1}で近似できる」とすると、e^{-1 \cdot \frac{kn}{m}}の形になり、右辺にあるe^{-kn/mがでてきます。

実際に使うときはmの大きさに注意する必要がありそうですね・・・

2007/12/09 06:21:45
  • id:koori
    すみません、質問文が変になってしまいました。

    リンク先はWikipediaの "ブルームフィルタ" のページ
    http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83%A0%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF

    数式は、リンク先の真ん中あたりにある
    > 全てが 1 となっている確率、すなわちブルームフィルタが誤ってある要素がメンバーであると判定してしまう確率は次のようになる。
    のすぐ下に書いてある数式ということでお願いします。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません