> The 5/8 probability mentioned is indeed correct. First element has four equiprobable possible outputs for its two hashes: (0,0), (0,1), (1,0) and (1,1) Thank

> The 5/8 probability mentioned is indeed correct. First element has four equiprobable possible outputs for its two hashes: (0,0), (0,1), (1,0) and (1,1) Thanks, that makes sense. I was thinking of states the filter could be in and ignored the different paths to get there. Now that I've had a chance to look at [0], it's interesting, but doesn't seem to matter for Bloom filters used in the normal way. > "Valid" configurations do not exist Sure, you can use any numbers you want, even negative ones. I take a more practical view, since Bloom filters make assumptions about choice (or derivation) of parameters. Given those assumptions, the formula criticized in [0] seems to work. Specifically: > [0]'s author claim that the difference may instead come from the real FPR value (which is actually very hard to compute, so it's hard to be sure). We know the FPR of any Bloom filter that actually exists. For a load factor l and number of hash functions k, it's l^k. The problem is that the FPR for the expected load factor of a set of parameters is lower than the expected FPR for those parameters, iff the expected load factor is greater than half. But the whole point of a Bloom filter is to have half the bits set; that's the magic that minimizes size and FPR. In practice you won't often have an expected load factor of exactly half, due to rounding. Depending on how you handle that, and whether you use asymptotics or an exact calculation, some drift in FPR makes sense. It'll be negligible as long as you're targeting half, though. n = 1, k = 2, m = 2 is noticeably off because at 3/4 it has a much higher expected load factor.