I am reading a network computer science lecture about the BLOOM FILTER and FALSE POSITIVE.
I have a hard time to understand the intermediate steps involved in a formula simplification.
The lecture explains that $(1- \frac 1 m)^{kn} \approx e^{-kn/m} $ (see page 7 in that document).
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}$.
Has anyone the solution?
Knowing that
$$\left(1- \frac 1 m\right)^m \to e^{-1} \tag{1}$$
it's as simple as
$$\left(1- \frac 1 m\right)^{kn} =\left(\left(1- \frac 1 m\right)^m\right)^{kn/m} \approx \left(e^{-1}\right)^{kn/m}=e^{-kn/m} \tag{2}$$
The first formula is a simple variation of $\left(1 + \frac 1 m\right)^m \to e $, which is a well known limit.
Edit: 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 \infty$ and $kn / m $ tends to some positive constant. But this might be unrealistic. A better derivation would use
$$ \left(1 - \frac 1 m \right)^m = e^{-1}\left( 1 + O(1/m) \right) $$
hence
$$ \left(1 - \frac 1 m \right)^{kn}=e^{-kn/m} (1 + O(1/m))^{kn/m}$$
This shows that, for the approximation to hold, it is sufficient that $m\gg1$ and $\frac{kn}{m^2}\ll 1$, or, equivalently, that $$m^2 \gg kn.$$