antennense

2022-07-11

Simplification step by step (exponential and logarithm) - regarding BLOOM FILTER - FALSE POSITIVE probability
$\left(1-\frac{1}{m}{\right)}^{kn}\approx {e}^{-kn/m}$
I don't get how to reach ${e}^{-kn/m}$ from $\left(1-\frac{1}{m}{\right)}^{kn}$
I have reviewed logarithm and exponent rules but I always get stuck, here is what I have tried; Starting from $\left(1-\frac{1}{m}{\right)}^{kn}$, I can write:
- ${e}^{\left(ln\left(1-\frac{1}{m}{\right)}^{kn}\right)}$
- ${e}^{\left(kn×ln\left(1-\frac{1}{m}\right)\right)}$
Or the other way around:
$ln\left({e}^{\left(1-\frac{1}{m}{\right)}^{kn}}\right)$
$ln\left({e}^{\left(1-\frac{1}{m}\right)×kn}\right)$
$ln\left({e}^{\left(1-\frac{1}{m}\right)}\right)+ln\left(kn\right)$
$\left(1-\frac{1}{m}\right)+ln\left(kn\right)$
After few steps I fall in an unsolvable loop hole playing with $ln$ and $e$ trying to reach ${e}^{-kn/m}$.

Mateo Carson

Knowing that
$\begin{array}{}\text{(1)}& {\left(1-\frac{1}{m}\right)}^{m}\to {e}^{-1}\end{array}$
it's as simple as
$\begin{array}{}\text{(2)}& {\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}\end{array}$
The first formula is a simple variation of ${\left(1+\frac{1}{m}\right)}^{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
${\left(1-\frac{1}{m}\right)}^{m}={e}^{-1}\left(1+O\left(1/m\right)\right)$
hence
${\left(1-\frac{1}{m}\right)}^{kn}={e}^{-kn/m}\left(1+O\left(1/m\right){\right)}^{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.$

Do you have a similar question?