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

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?

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