My Bloom Filter's Exact Formula Returned 1e+227 Per Cent

A Bloom filter makes exactly one promise and keeps it absolutely: no false negatives. Everything else is a rate you are choosing, whether or not you realise it.

👉 Live, every number measured in your browser: https://dev48.in/solve/day82-bloom-filter.html

The formula everyone quotes is optimistic

p = (1 − e^(−kn/m))^k

It assumes the k bits a key sets are independent. They are not, and it is a limit result. At a fixed m/n ratio of 6.4, with only the size changing:

filter	textbook	exact	error	direction
m=64, n=10	4.6648%	4.7236%	−1.25%	optimistic
m=128, n=20	4.6648%	4.6938%	−0.62%	optimistic
m=256, n=40	4.6648%	4.6792%	−0.31%	optimistic
m=1024, n=160	4.6648%	4.6684%	−0.08%	optimistic

Small, but optimistic — the wrong direction for a structure you chose in order to bound a risk.

My first "exact" formula was nonsense

I implemented the closed-form inclusion–exclusion sum over Stirling numbers. In log space, carefully. It returned things like:

m=128, n=20   exact: 6054371110260.6855%
m=1024, n=160 exact: 1.0090609022115038e+227%

A rate above 1 is not a rounding problem. It is a wrong function. exp(logC(m,i)) is astronomically large while the alternating sum beside it is tiny, so the two cancel to noise.

The self-check that caught it is embarrassingly simple, and I had not written it until this happened:

t("every exact rate is a probability - in [0, 1]", () => {
  for (const [m, k, n] of CASES) {
    const v = pExact(m, k, n);
    if (!(v >= 0 && v <= 1)) return false;
  }
  return true;
});

The replacement carries a probability distribution instead, so every number stays in [0,1] and nothing cancels:

function occupancy(m, k, n) {
  let dist = new Float64Array(m + 1);
  dist[0] = 1;
  for (let step = 0; step < n; step++) {
    const next = new Float64Array(m + 1);
    for (let i = 0; i <= m; i++) {
      if (dist[i] < 1e-300) continue;
      for (let j = 0; j <= k; j++) {           // j NEW bits, hypergeometric
        const t = lchoose(i, k - j) + lchoose(m - i, j) - lchoose(m, k);
        if (isFinite(t)) next[i + j] += dist[i] * Math.exp(t);
      }
    }
    dist = next;
  }
  return dist;
}

Self-collision is exactly zero, and that changes the model

I expected a key's own k probes to sometimes land on each other, more often at higher k. Measured: zero, at every k.

That is not a measurement error. With double hashing g_i(x) = h₁ + i·h₂ (mod m) and an odd h₂ on a power-of-two m, the step is invertible mod m, so i·h₂ is distinct for every i < m. The probes cannot collide.

Which means the right model for a stranger is C(i,k)/C(m,k) — k distinct positions landing inside the set bits — not (i/m)^k.

On a modulus that is not a power of two, self-collision does appear. The guarantee is a property of the modulus, not of double hashing.

And the rate only holds if the hash avalanches

Every number above assumes probes land uniformly. Swap FNV-1a for raw djb2 — a hash everyone has typed from memory — and:

filter	model	djb2 + avalanche	djb2 RAW	raw / model
m=256, k=3, n=40	0.052	0.053	0.208	4.0×
m=1024, k=5, n=100	0.0086	0.0087	0.0493	5.7×
m=2048, k=6, n=200	0.0076	0.0076	0.0109	1.4×

djb2's low bits are a function of the previous low bits and one character — a weak mixer — and a power-of-two modulus uses only the low bits. One Murmur3 finaliser, which adds no entropy at all, fixes it completely.

The nastiest part: fill is 0.3730 raw against 0.3887 mixed, with 0.3863 predicted. The damage is which bits, not how many, so every occupancy check passes while the false-positive rate is five times what you computed. And the factor is seed-dependent — 1.2× in one configuration, 5.7× in another. It can look fine in the setup you tested and be five times off in the one you shipped.

Checked exhaustively

For tiny filters, every possible placement of every key is enumerated and the false-positive rate computed by direct counting — no formula involved:

filter	exhaustive	DP
m=6, k=2, n=1	0.06666667	0.06666667
m=6, k=2, n=2	0.27111111	0.27111111
m=8, k=3, n=2	0.17889031	0.17889031
m=10, k=2, n=3	0.21689986	0.21689986

53 verifier asserts, 0 failures. 24 in-page checks.