Bloom Filter 2D: Occupancy & False-Positive Statistics

Bit Array

Array size m 128

Hash functions k 4

Insertions

Items inserted n 0

Ensemble Readouts (250 filters)

Exact P(false positive)

0.0%

Exponential approx.

0.0%

Monte Carlo measured

0.0%

Exact − approx. gap

0.0 pp

Mean fraction of bits set (exact vs measured)

0.0% / 0.0%

How this 2D model differs from the 3D view

The 3D simulator inserts real words through a real hash function (FNV-1a) into one filter and reports its actual behaviour. This 2D companion instead models the underlying combinatorial process that the textbook Bloom filter formula is derived from — a "balls-into-bins" occupancy problem — and runs it as a Monte Carlo ensemble of 250 independently simulated filters, so the theory can be checked statistically rather than anecdotally.

Per insertion, per filter: throw k balls into m bins uniformly at random (i.i.d.)

P(a given bit still 0 after kn throws) = (1 − 1/m)^(kn)         ← EXACT, combinatorial
                                        ≈ e^(−kn/m)              ← asymptotic approximation (m → ∞)

P(false positive) = (1 − P(bit=0))^k

Both curves on the plot are computed analytically from m, k and n. The dots are a genuine Monte Carlo measurement: at the current n, every one of the 250 simulated filters is queried with 24 fresh random k-bin draws that were never inserted, and the fraction reporting "present" is the measured false-positive rate — the third, independent way of arriving at the same number. The bottom strip is a live histogram of the fraction of bits set across all 250 filters at the current n: its narrowing spread as m·k grows is the concentration-of-measure effect that makes the exact formula a reliable predictor for any single large real-world filter, even though each filter's own bit array is one random outcome.

Exact vs approximation gap — (1−1/m)^(kn) is not the same function as e^(−kn/m); they agree only in the m→∞ limit. This model plots both so the (usually small, but nonzero) systematic error from using the common exponential shortcut is visible directly, for the array sizes real filters actually use.
Array size m / hash count k — rebuild the whole 250-filter ensemble from scratch and recompute both analytic curves.
Items inserted n — replays every filter's insertion history up to n (bits only ever turn on, so decreasing n resets and replays).

Exact P(FP) Exponential approx. Monte Carlo measured Current n