# If m is the number of bits in the array, k is the number of hash functions and we have

If $m$ is the number of bits in the array, $k$ is the number of hash functions and we have $n$ entries, then the false positive probability upper bound can be approximated as:
$\left(1-{e}^{\frac{-kn}{m}}{\right)}^{k}$
It further states in the wiki article that:
"The number of hash functions, $k$, must be a positive integer. Putting this constraint aside, for a given $m$ and $n$, the value of $k$ that minimizes the false positive probability is:"
$k=\frac{m}{n}\mathrm{ln}2$
How can I find the $k$ value that minimizes the false positive function ?
You can still ask an expert for help

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

treccinair
Let $f\left(k\right)=\left(1-{e}^{\frac{-kn}{m}}{\right)}^{k}=\left(1-{e}^{ak}{\right)}^{k}$ where $a=-n/m$
Then

Let $1-{e}^{ak}=y$, so $k=\mathrm{ln}\left(1-y\right)/a$.
Then $\left(1-{e}^{ak}\right)\mathrm{ln}\left(1-{e}^{ak}\right)=ka{e}^{ak}$ becomes $y\mathrm{ln}\left(y\right)=\left(\mathrm{ln}\left(1-y\right)/a\right)\left(1-y\right)$ or ${y}^{y}=\left(1-y{\right)}^{\left(1-y\right)/a}$.

We have step-by-step solutions for your answer!

Ryan Robertson
You helped me with the same problem, thanks!

We have step-by-step solutions for your answer!