Bloom Filter: Exponential Precision for Linear Space

ε ≈ (1/2)^(b·ln 2) | b = bits per inserted object | False positives shrink exponentially as b grows linearly

Bit Array (100 bits)

Inserted: (none)

Filter Parameters

b (bits/obj) 8

Hash fns k —

False pos ε —

FORMULA

k = round(b · ln 2)

ε = (0.5)^(b · 0.693)

b=8 → ε ≈ 2% | b=16 → ε ≈ 0.02%

False Positive Rate vs Bits/Object