# Achieving better than the theoretical False Positive Rate for Bloom Filters

I implemented a standard Bloom Filter in C++, and tested it on different sizes, with varying values of the ratio ${c = n/m}$ where ${n}$ is the size of the filter, and ${m}$ is the number of elements inserted.

For a Bloom Filter, I created ${k}$ Hash functions, and set the value in the filter for each Hash Index returned. Here's a graph of the results I obtained from my tests:

The problem from the graph is clear, I am getting False Positive rates that are better than the Theoretical value. The theoretical value is based on the assumption that each Hash Index is equally likely, which is:

$Pr(H(a) = 1)^k = 1 - Pr(H(a) = 0)\\ = (1 - (1 - 1/n)^{km})^{k}\\ = (1 - e^{-k/c})^{k}$

Using $k = c \ln(2)$

$Pr(H(a) = 1)^{k} = (1 - e^{-\ln(2)})^{k}\\ = (1/2)^{c \ln(2)}\\ = 0.6185^{c}$

All my tests are based on the optimal value of $k = c \ln(2)$, and the theoretical line is a plot of $0.6185^{c}$. My concern is that my False Positive rates are consistently better than the theoretical. Does this mean that my implementation is incorrect, or is it a likely possibility given the large sizes of the Bloom Filters and the efficiency of the hashing algorithm?

I appreciate any guidance on this.

The approximation of probability you are calculating is used to give estimated optimal number of hash function used (which is then rounded, $c*ln(2)$ does not look like integer).

There are many factors that should be considered: the choice of hash functions, data set provided for tests, approximation skew, rounding of approximation and fact that given theoretical bound is asymptotic value, so works better for bigger n and m.

I would like to propose paper false-positive rate of Bloom filters, showing how given approximation is incorrect.
Another good resource Thomas Gerbet, Amrit Kumar, C´edric Lauradoux. The Power of Evil Choices in Bloom Filters. (Research Report) RR-8627, INRIA Grenoble. 2014 shows how saturation of filter changes with given data.

• Are you sure that independent hash bits is a worst-case bound? Won't independent data produce fewer false positives than dependent data, but more false positives than negatively dependent data? – jbapple Mar 29 '16 at 15:18
• @jbapple I revoke it, both versions were flawed (with heavy unclearity on top), and the problem is in different place, so I just rewrote the answer. – Evil Mar 30 '16 at 4:32

$$(1 - (1 - 1/n)^{km})^{k} = (1 - e^{-k/c})^{k}$$