Every other Probabilistic entry on this site that summarizes a stream in fixed memory — HyperLogLog, Count-Min Sketch, Count Sketch, Bloom Filter, Cuckoo Filter, XOR Filter — needs to hash whatever item just arrived, because the question being answered is always about which items: has this one been seen, how many times, how many distinct ones. The Morris Counter, published by Robert Morris in 1978 ("Counting Large Numbers of Events in Small Registers," decades before any of those), answers a question with no item identity in it at all: roughly how many events have happened, total, in a stream too long to tally exactly with the bits on hand? It doesn't take an item as input, doesn't hash anything, and doesn't care whether two events were "the same" — it counts ticks, not things.
The trick: keep a single small counter c, starting at 0. On every event, increment
c by 1 — but only with probability 1/2^c, decided by one fresh random
draw. Early on that probability is 1 (guaranteed) and drops fast: 1, then 1/2, then 1/4, then 1/8,
and so on. The counter itself no longer holds the true count — it holds roughly log2(n)
after n events — and the actual estimate is read back out as 2^c - 1.
Trading an exact tally for an estimate is what buys the tiny footprint: a counter that needs to
track up to a billion events exactly needs 30 bits; one that only needs to track up to
log2 of a billion — about 30 — needs just 5 bits to hold c itself, worked
out exactly in Complexity below.
A fixed 16-event stream feeding one Morris Counter, using a seeded random generator so the trace
is identical every time you replay it. Click Next to feed one event at a time and
watch the draw: the counter climbs to 1 then 2 on the first two events (both guaranteed, since
p=1 then p=1/2), stalls at 2 for three events, jumps to 3, stalls for
five, jumps to 4, then stalls for the rest of the stream — ending at c=4, an estimate
of 2^4 - 1 = 15 against a true count of 16.
1/2^c, bump c
by 1. O(1) time, one random draw, one comparison, at most one write — and unlike a
plain tally, the state itself (c) never grows past roughly log2(n), no
matter how long the stream runs.2^c - 1 back out. Valid after any number of
increment calls, not just at some defined "end" — there's no such thing as a final
state the counter is waiting for.c has climbed past what a handful of individual events could have produced — the
counter has already forgotten how it got to c, only that it did.Let Y_n = 2^{c_n} after n events. The claim: E[Y_n] = n + 1
for every n, which makes E[2^{c_n} - 1] = n exactly — the estimator has no
systematic bias in either direction. Base case n = 0: c_0 = 0,
Y_0 = 1 = 0 + 1. Inductive step: assume E[Y_n] = n + 1. Event
n+1 arrives; with probability 1/Y_n (since 1/2^{c_n} = 1/Y_n)
the counter increments and Y doubles, otherwise Y is unchanged. So,
conditioned on the current value of Y_n:
E[Y_{n+1} | Y_n] = (1 - 1/Y_n)·Y_n + (1/Y_n)·2Y_n
= Y_n - 1 + 2
= Y_n + 1Taking expectation over Y_n itself: E[Y_{n+1}] = E[Y_n] + 1 = (n+1) + 1 =
(n+1) + 1, matching the claim at n+1. The increment probability was
deliberately built to be exactly 1/Y_n — the algebra above is why that
specific choice, and not some other decreasing schedule, is the one that keeps E[Y_n]
climbing by precisely 1 per event. The off-by-one pitfall below shows,
both algebraically and measured live, what happens the moment that probability is shifted by even
one factor of 2.
class MorrisCounter {
#c = 0;
increment() {
const p = 1 / Math.pow(2, this.#c);
if (Math.random() < p) {
this.#c++;
return { incremented: true, c: this.#c };
}
return { incremented: false, c: this.#c };
}
estimate() {
return Math.pow(2, this.#c) - 1;
}
}Verified three ways, all in Node before any page prose was written. (1) The exact shipped demo
trace — all sixteen increment calls with the page's fixed seed reproduced standalone,
step by step: increments at events 1, 2, 6, and 12, stalling in between, ending
c=4, estimate 15 — matching the page's prose exactly. (2) A 20,000-trial sweep at
n=100 using real Math.random(), not the demo's fixed seed: mean estimate
99.94 against a true count of 100, and a measured standard deviation of 70.91 against the closed-form
prediction √(n(n+1)/2) = 71.06 — both the unbiasedness and the variance formula
land where the induction and a known second-moment derivation say they should, not just "roughly
in the neighborhood." (3) Averaging 16 independent counters over 5,000 trials at the same
n=100: mean 99.6, standard deviation 17.65 against the predicted
71.06/√16 = 17.77 — confirming the variance really does shrink like
1/√k for k independent counters, the standard real-world fix for a
single counter's wide spread. See /tmp/morris/sim.js and
/tmp/morris/stats.js, scratch, not committed.
Unbiased does not mean tight. A single Morris counter's estimate really is
correct on average, but any one run can land far from the true count — the induction above proves
the mean, not the spread. Run the sweep below yourself: at n=100, a lone counter's
estimate has a standard deviation over 70, more than two-thirds of the true count
itself. Real deployments never rely on one counter alone — they keep several independent counters
and average the estimates, which is the second row below, shrinking the spread by
1/√k for k counters at the cost of k times the state
(still tiny — k times a handful of bits, nowhere near an exact tally).
Shifting the increment probability by one factor of 2 provably halves the estimate — not
approximately, exactly, in expectation. A tempting one-character slip is computing the
probability as 1/2^(c+1) instead of 1/2^c — "the counter is about to
become c+1, so shouldn't the odds be based on that?" Redo the induction above with
this probability instead: conditioned on Y_n, the counter now increments with
probability 1/(2Y_n), so E[Y_{n+1} | Y_n] = Y_n·(1 - 1/(2Y_n)) +
2Y_n·(1/(2Y_n)) = Y_n + 1/2 — a constant 1/2 per event instead of 1,
regardless of the current value of Y_n. That telescopes to E[Y_n] = 1 + n/2,
so the estimate Y_n - 1 averages out to exactly n/2: a systematic,
provable, exact halving, not noise. Run the sweep below and watch the third row land at roughly half
the true count every time — the bug doesn't throw, doesn't look obviously wrong on any single run
(it's still a plausible-looking number, still growing with the stream), and is only exposed by
checking the mean against a known value across many runs, the same category of pitfall as Reservoir Sampling's own off-by-one.
| Variant | Mean estimate | Std dev |
|---|---|---|
| Not run yet — click above. | ||
The counter itself is not the estimate. Reading c directly and
treating it as "roughly how many events" is a different, much cruder error than any bug above — at
n=100, correct c typically lands around 6 or 7, nowhere near 100.
estimate()'s 2^c - 1 conversion is not optional decoration; the whole
point of paying for randomness is to make that conversion an unbiased estimator of n,
and skipping it throws that away for a number with no defined meaning at all.
c only needs to reach 8 to represent an estimate
near 2^255, long after any realistic event count.1/2^c, not on every
event — at any non-trivial c, most increments skip the write (and the contention)
entirely, in exchange for the same estimate-not-exact-count trade made everywhere else on this
page.Time: O(1) per event — one random draw, one comparison, at most one
increment, regardless of how many events have already been seen. Space: to count
up to n events, an exact counter needs O(log n) bits; a Morris Counter's
c only needs to climb to around log2(n), which itself only takes
O(log log n) bits to represent. Concretely: counting exactly up to one billion events
needs 30 bits; the Morris Counter's c only needs to reach about 30, which fits in 5
bits — a 6× reduction here, and the gap between O(log n) and
O(log log n) only widens as n grows further.
This site's guide, Choosing a Probabilistic Structure, places this entry among the other fixed-memory stream summarizers — including the one respect in which it's simpler than all of them: it's the only one that needs no hash function at all, because it never has to tell one item apart from another.