• The probability that a specific bit remains 0 after inserting n elements using k hash functions: $\left(1 - \frac{1}{m}\right)^{kn}$
• The probability that all k bits queried are 1, resulting in a false positive: $\left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k$

<aside> 💡

$\left( 1-\frac{1}{m} \right)^{kn} \to e^{-kn/m}$ when $m\to \infty$

</aside>

• The approximate false positive rate using the exponential approximation: $p = \left(1 - e^{-kn/m}\right)^k$
• The optimal number of hash functions that minimizes the false positive rate: $k = \frac{m}{n} \ln 2$
• The required size of the bit array to achieve a target false positive rate p for n elements: $m = -\frac{n \ln p}{(\ln 2)^2}$