False Positive Rate

The classic Bloom math from Bloom (1970). After inserting n items into an m-bit array using k hash functions, a particular bit is still 0 with probability:

(1 - 1/m)^(kn)  ≈  exp(-kn/m)

A query for an item never inserted returns MAYBE iff ALL k bits happen to be 1 by collision:

fp_rate = (1 - exp(-kn/m))^k

Optimizing m, k for a target false-positive rate p

Differentiate; set the gradient to zero. You get:

m_opt = ceil( -n * ln(p) / (ln(2)^2) )        # smallest m achieving FP rate p for n items
k_opt = round( (m / n) * ln(2) )              # k at this m

Rule of thumb: ~10 bits/item gives ~1% FP rate; ~15 gives ~0.1%; ~20 gives ~0.01%. Each extra ~4.8 bits/item knocks one more 10x off the FP rate.

What the numbers actually look like

What happens past N

The fp_rate formula assumes n items were inserted. If you blow past n (the value you sized for), kn/m grows, the bit-set probability climbs toward 1, and FP rate explodes toward ~100%. We'll come back to this in the monitoring lesson.

In this problem you'll implement: OPTIMAL (compute m, k from target FP and n), FP (compute the actual FP rate for given m, n, k), and BPI (bits-per-item required for a target FP).