14
$\begingroup$

According to this survey paper on Bloom Filters, we can do the following approximation

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

which allegedly is a $O(\frac 1m)$ approximation. I am curious as to why this is so. I know that:

  • $(1 - \frac{1}{x})^x$ eventually converges to $e^{-1}$ because of L'Hospital's rule.

  • $(1 - \frac{1}{x})^x$ can be expressed as $e^{-1} \prod_{i=1}^{\infty} e^{\frac{-1}{(i+1)x^i}} $ using a Taylor expansion.

However, I don't see a clean way of showing that it is a $O(\frac 1m)$ approximation.

$\endgroup$

migrated from cs.stackexchange.com Oct 18 '17 at 18:17

This question came from our site for students, researchers and practitioners of computer science.

19
$\begingroup$

We have: $$ \left(1 - \frac{1}{x}\right)^x = e^{x\log\left(1-\frac{1}{x}\right)} = e^{x\left(-\frac{1}{x}-\frac{1}{2x^2}+o\left(\frac{1}{x^2}\right)\right)} = e^{\left(-{1}-\frac{1}{2x}+o\left(\frac{1}{x}\right)\right)}$$

by Taylor expansion of $\log(1-t)$ at $0$. Then by expanding the exponential : $$ e^{\left(-\frac{1}{2x}+o\left(\frac{1}{x}\right)\right)} = 1-\frac{1}{2x}+o\left(\frac{1}{x}\right) + o\left(\frac{1}{x}\right) = 1+O(1/x) $$

So that plugging everything back: $$\left(1 - \frac{1}{x}\right)^x = e^{-1}(1+O(1/x)) = e^{-1}+O(1/x)$$

$\endgroup$
  • $\begingroup$ Ahh I should have discarded the higher order terms for an asymptotic. Thank you! $\endgroup$ – iart Oct 17 '17 at 22:59
  • $\begingroup$ @iart I am not sure what you did, but the asymptotic should be exactly the same even if you keep higher-order terms. That is always the case with O-notation arithmetic. $\endgroup$ – Federico Poloni Oct 18 '17 at 6:45
  • $\begingroup$ If you have more terms in the bigO you can collapse them, for instance, $O(1/x^2)+O(1/x^3)$ is a $O(1/x^2)$. Doing the computations with an arbitrary long Taylor expansion should yield the same result in the end. If you're happy with this answer, please mark it as Solved! $\endgroup$ – user70925 Oct 18 '17 at 8:51
  • $\begingroup$ Oh, wow, changing sign inside the brackets changes sign in power of $e$. $\endgroup$ – rus9384 Oct 18 '17 at 9:01
  • $\begingroup$ Yup marked it as solved. $\endgroup$ – iart Oct 19 '17 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.