antennense

Answered

2022-07-11

Simplification step by step (exponential and logarithm) - regarding BLOOM FILTER - FALSE POSITIVE probability

$(1-\frac{1}{m}{)}^{kn}\approx {e}^{-kn/m}$

I don't get how to reach ${e}^{-kn/m}$ from $(1-\frac{1}{m}{)}^{kn}$

I have reviewed logarithm and exponent rules but I always get stuck, here is what I have tried; Starting from $(1-\frac{1}{m}{)}^{kn}$, I can write:

- ${e}^{(ln(1-\frac{1}{m}{)}^{kn})}$

- ${e}^{(kn\times ln(1-\frac{1}{m}))}$

Or the other way around:

$ln({e}^{(1-\frac{1}{m}{)}^{kn}})$

$ln({e}^{(1-\frac{1}{m})\times kn})$

$ln({e}^{(1-\frac{1}{m})})+ln(kn)$

$(1-\frac{1}{m})+ln(kn)$

After few steps I fall in an unsolvable loop hole playing with $ln$ and $e$ trying to reach ${e}^{-kn/m}$.

Answer & Explanation

Mateo Carson

Expert

2022-07-12Added 15 answers

Knowing that

$\begin{array}{}\text{(1)}& {(1-\frac{1}{m})}^{m}\to {e}^{-1}\end{array}$

it's as simple as

$\begin{array}{}\text{(2)}& {(1-\frac{1}{m})}^{kn}={\left({(1-\frac{1}{m})}^{m}\right)}^{kn/m}\approx {\left({e}^{-1}\right)}^{kn/m}={e}^{-kn/m}\end{array}$

The first formula is a simple variation of ${(1+\frac{1}{m})}^{m}\to e$, which is a well known limit.

As pointed out in a comment, this derivation does not specify how the parameters $n$, $m$, $k$, should be related for the asymptotics to hold. A simple requirement would be that $m\to \mathrm{\infty}$ and $kn/m$ tends to some positive constant. But this might be unrealistic. A better derivation would use

${(1-\frac{1}{m})}^{m}={e}^{-1}(1+O(1/m))$

hence

${(1-\frac{1}{m})}^{kn}={e}^{-kn/m}(1+O(1/m){)}^{kn/m}$

This shows that, for the approximation to hold, it is sufficient that $m\gg 1$ and $\frac{kn}{{m}^{2}}\ll 1$, or, equivalently, that

${m}^{2}\gg kn.$

Most Popular Questions