人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

[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]
の両辺がほぼ等しい理由を教えて下さい。

●質問者: koori
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:TEX フィルタ ブルーム リンク
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● quintia
●100ポイント ベストアンサー

\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 を代入した形です。

◎質問者からの返答

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ