How is the optimal number of hashes is derived in bloom filter?

Question

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?

Answer 1

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$.