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.
Achieving better than the theoretical False Positive Rate for Bloom Filters
algorithms;data structures;statistics;bloom filters
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, Cedric 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.