Deriving the False-Positive Probability

In one line

After n insertions with k hashes into m bits, a given bit is still 0 with probability (1 − 1/m)^(kn) ≈ e^(−kn/m). A false positive needs all k probed bits to be 1, so p ≈ (1 − e^(−kn/m))^k. Understanding each step lets you reason about any variant.

0/4 · 0%

Think of it like this

Throwing darts at a board of m numbered squares. After throwing kn darts at random, some squares are still untouched. A stranger picks k squares at random; if every one of them has a dart in it, you'd wrongly think the stranger had thrown there.

Key ideas

01
Step 1, one hash misses a given bit: a single hash sets a particular bit with probability 1/m, so it leaves it 0 with probability 1 − 1/m.
02
Step 2, all insertions miss it: n items × k hashes = kn independent attempts, so P(bit still 0) = (1 − 1/m)^(kn). Using (1 − 1/m)^m ≈ e^(−1) for large m, this is ≈ e^(−kn/m).
03
Step 3, a bit is 1: P(bit = 1) ≈ 1 − e^(−kn/m). This is the fill ratio (fraction of bits set) you can also measure directly.
04
Step 4, false positive: a non-member's k positions are (assumed) independent and uniform, and it's a false positive only if all k are 1: p ≈ (1 − e^(−kn/m))^k.
05
Assumptions to name: hashes are uniform and independent, m is large. Real filters match this closely with good hashing; the exact formula (Bose et al.) differs slightly for small m, and the approximation slightly underestimates p there.

Code & diagrams

derivation.txttext

P(one hash leaves bit b at 0)          = 1 - 1/m
P(all kn hashes leave bit b at 0)      = (1 - 1/m)^(kn)  ~  e^(-kn/m)
P(bit b is 1)                          ~  1 - e^(-kn/m)          <- fill ratio
P(all k bits of a non-member are 1)    ~  (1 - e^(-kn/m))^k      <- false-positive rate p

Example: n = 1,000,000   m = 9,585,059 bits   k = 7
  kn/m = 0.7303   e^-0.7303 = 0.4818   fill = 0.518
  p = 0.518^7 = 0.0100  (1.00%)

measure_fpr.pypython

import math, random, string
from tiny_bloom import TinyBloom           # from Topic 0.3

n, m, k = 20_000, 191_702, 7                # sized for ~1%
bf = TinyBloom(m, k)
members = {''.join(random.choices(string.ascii_letters, k=12)) for _ in range(n)}
for x in members: bf.add(x)

trials, fp = 100_000, 0
for _ in range(trials):
    q = ''.join(random.choices(string.ascii_letters, k=13))   # length 13: never a member
    fp += bf.might_contain(q)
print(f"measured {fp/trials:.4%}  predicted {(1-math.exp(-k*n/m))**k:.4%}")
# measured 1.0120%  predicted 1.0036%

Interview problem

The problem

Derive p on the whiteboard

Without notes, derive the false-positive probability of a Bloom filter with n items, m bits and k hash functions, and state the assumptions.

Explain it without notes

Why is 1 − e^(−kn/m) called the fill ratio, and how can you use it in production?

Practice

Compute p for n = 1M, m = 8M bits, k = 5 by hand.

Trade-offs

↔
The formula assumes ideal hashing; real filters match it only if hashing is good (Phase 2).

Done when you can

I can derive p ≈ (1 − e^(−kn/m))^k and state its assumptions.

Command Palette