> 6 days after I started to write this post, it is proved that the math behind false positive probability was wrong for 50 years
This isn't true.
The "Bloom math is wrong!" clamor started at least 12 years ago with [1], which brazenly cites Bloom, then proceeds to give an analysis of Knuth's subtly different filter from TAOCP instead.
There are issues with [1], but its exact false positive formula was eventually proven correct. Its argument is incompatible with Bloom's original filter, though, and Knuth explicitly states that the false positive formula he gives is approximate.
In other words, nothing was proved wrong. The analysis doesn't apply to Bloom and doesn't contradict Knuth.
Now, [1] may be the first paper to give the exact false positive formula for Knuth's filter (and Bloom's was given in 1979 by [2]), so it's not entirely without merit. But in practice none of this matters anyway. At useful sizes the approximations are accurate. Knuth's is a lower, Bloom's an upper bound, and the two become functionally equivalent very quickly.
I believe I jumped into conclusion without properly reading the article I linked and the first reference you gave. I will update my post not to give any false information. Thank you!
In many applications, such as filtering queries to a data store (Figure 1), the Bloom filter will start out empty and fill as items are added to the data store and inserted into the Bloom filter. The false positive rate will be very low and then increase non-linearly as the Bloom filter fills. The average false positive rate over the life of the filter is much lower than the design false positive rate for the full filter given by the math.
> 6 days after I started to write this post, it is proved that the math behind false positive probability was wrong for 50 years
This isn't true.
The "Bloom math is wrong!" clamor started at least 12 years ago with [1], which brazenly cites Bloom, then proceeds to give an analysis of Knuth's subtly different filter from TAOCP instead.
There are issues with [1], but its exact false positive formula was eventually proven correct. Its argument is incompatible with Bloom's original filter, though, and Knuth explicitly states that the false positive formula he gives is approximate.
In other words, nothing was proved wrong. The analysis doesn't apply to Bloom and doesn't contradict Knuth.
Now, [1] may be the first paper to give the exact false positive formula for Knuth's filter (and Bloom's was given in 1979 by [2]), so it's not entirely without merit. But in practice none of this matters anyway. At useful sizes the approximations are accurate. Knuth's is a lower, Bloom's an upper bound, and the two become functionally equivalent very quickly.
1. https://cglab.ca/~morin/publications/ds/bloom-submitted.pdf
2. Algorithm-A in https://sci-hub.tw/10.1109/proc.1979.11543