This paper claims that the traditional analysis of the error rate in Bloom filters is incorrect, then provides a lengthy and nontrivial analysis of the actual error rate. The linked paper was published in 2010, yet I've seen the traditional analysis of Bloom filters continued to be taught in various algorithms and data structures courses.
Is the traditional analysis of Bloom filters indeed incorrect?
Thanks!
The traditional analysis is fine. The "traditional" analysis is, if it is explained correctly, an approximation; it's based on calculating the expected number of cells that are 0/1 when you hash the keys into the filter, and then analyzing as though that was the actual number. The point is that the number of cells that are 0 (or 1) are tightly concentrated around their expectation, so it's a fine approximation. This was well known, and can be found, I think, even back in my survey article with Andrei Broder.
This paper says that really the performance of a Bloom filter is a random variable (corresponding to the actual fraction of 0/1 entries), and if you want to calculate that performance exactly for some reason, you need to do the combinatorics. For smaller filters, you'll see an arguably non-trivial difference.
I've talked with the authors of this paper. Their analysis is all well and good (though I'd argue that it isn't deep or new); their motivation that the "traditional analysis is wrong" was, I think, exaggerated.
Let me add to Michael's answer that for split Bloom filters, where the hash functions have disjoint ranges, the traditional analysis is indeed correct without approximation or any concentration bounds. This is because the error probabilities for different hash functions become independent rather than correlated. The space/error trade-off for split Bloom filters is essentially the same as for traditional Bloom filters, so I think this is a good variant for teaching.
