What you're seeing
The horizontal axis is the true count n as a stream of events arrives; the vertical axis is the estimate. A perfect counter would ride the green diagonal exactly. Each faint line is one Morris counter — and they wander, jumping in bigger and bigger steps, sometimes well above or below the truth. But their mean (blue) tracks the diagonal closely. Drag Parallel counters up and watch the blue line tighten onto the green: that convergence is the theorem, drawn.
This is the atlas's first approximate algorithm. Its answer isn't a number, it's a distribution — so its "soul" isn't an invariant but a guarantee.
The rule
init: X = 0 increment: with probability 2^(-X): X = X + 1 query: estimate = 2^X − 1
Early on (X small) almost every event bumps X; once X is large, a bump needs a rare coincidence — so X grows roughly like log₂ n, and storing X takes only about log₂ log₂ n bits. A counter that would need 4 bytes to reach 4 billion fits in about 5 bits.
The guarantee
There is no invariant pinning the estimate to the truth — instead there is a guarantee in expectation: E[2^X − 1] = n, exactly. The proof is a one-line induction. Let C = 2^X. After an increment, X rises by one with probability 2^(−X), so E[C_{new} | X] = (1 − 2^(−X))·2^X + 2^(−X)·2^(X+1) = 2^X + 1 = C + 1. Each event adds exactly 1 to the expected value of C; since C starts at 2^0 = 1, after n events E[C] = n + 1, hence E[2^X − 1] = n. The estimator is unbiased. Its variance is n(n−1)/2, so a single counter's relative error is around 1/√2 ≈ 71% — large. Averaging m independent counters keeps it unbiased and divides the variance by m, shrinking the relative error to ≈ 0.71/√m. That is the faint-lines-versus-blue-line story on the canvas, and it is exactly what this entry's test checks statistically across thousands of seeded runs.
The cost
The whole point is the space row: an exact counter for n needs ⌈log₂ n⌉ bits; Morris needs ≈ log₂ log₂ n. The readout shows this shrink live (e.g. 12 bits → 4). That exponential saving is irrelevant for one counter — but decisive when you must keep millions of counters in fast memory, which is exactly the streaming setting.
In the wild
Morris invented this in 1978 at Bell Labs to count large numbers of events in a small (8-bit) register. The idea — trade exactness for exponential space savings, and recover accuracy by averaging — is the seed of the entire streaming / sketching field. Its direct descendants are the cardinality estimators Flajolet–Martin and HyperLogLog (which count distinct items in tiny space and run inside Redis, Presto, BigQuery, and Druid for "how many unique users?" queries), and the frequency sketches like Count–Min. The base can be tuned (a base-a "Morris-α" counter) to trade more space for less variance. Whenever you see an approximate-but-cheap counter in a database or a network monitor, this is its ancestor.
Try this
Set Parallel counters to 1 and run it a few times with New run: a single counter is wildly noisy, often 30–70% off. Now slide it to 64 and watch the blue mean lock onto the green truth. You're watching variance fall as 1/√m — the reason real systems average many sketches.
References
- Morris, R. "Counting large numbers of events in small registers." Communications of the ACM 21(10):840–842, 1978. The original.
- Flajolet, P. "Approximate counting: a detailed analysis." BIT 25:113–134, 1985 — the rigorous variance analysis.
- Andoni, A. Advanced Algorithms (Columbia COMS 4995-8, 2021), Lecture 1 — approximate counting / Morris. course materials.
- Flajolet, Fusy, Gandouet & Meunier. "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm." AofA, 2007 — a descendant in the wild.