2
$\begingroup$

As mentioned in several resources such as Wikipedia the optimal number of hash functions for a bloom filter is known to be $$k=\frac{m}{n} \ln 2$$ but how is this number derived? It seems that it's the number that minimizes the false positive rate which is equal to $$(1-(1-\frac{1}{m})^{kn})^k$$ Can anybody explain the steps to find the argmin of the FP rate?

$\endgroup$

1 Answer 1

2
$\begingroup$

We want to find the value of $k$ that minimizes the function $$ f(k) = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k. $$ When $m$ is large, $1 - 1/m \approx e^{-m}$, and so $$ f(k) \approx \left(1 - e^{-kn/m}\right)^k. $$ The logarithm of this is $$ \log f(k) \approx k \log(1-e^{-kn/m}). $$ The derivative of this approximation is $$ \log(1 - e^{-kn/m}) + k \frac{\frac{n}{m}e^{-kn/m}}{1-e^{-kn/m}} = \log(1 - e^{-kn/m}) + \frac{kn}{m} \frac{e^{-kn/m}}{1-e^{-kn/m}}. $$ Let $x = e^{-kn/m} \in (0,1)$. The derivative is thus $$ \log (1-x) - \log x \frac{x}{1-x} = \frac{(1-x)\log(1-x)-x\log x}{1-x}. $$ It is not hard to check that the numerator is positive for $x<1/2$, zero at $x=1/2$, and negative for $x>1/2$. This means that when $k < \frac{m}{n}\log 2$, the approximation to $f(k)$ is decreasing, and when $k > \frac{m}{n}\log 2$, it is increasing. It thus reaches a minimum when $k = \frac{m}{n} \log 2$.

$\endgroup$

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.