Morris Approximate Counting

Counting by Occasionally Incrementing

An exact counter adds one for every event. Morris counting asks a stranger question: what if the stored counter advances less often as it grows? Early increments happen frequently; later increments are rare. The state is then best read as an exponent rather than as the count itself.

Imagine a notebook with numbered milestones. At state $C=0$, record the next arrival with probability $1$. At $C=1$, record an arrival with probability $1/2$; at $C=2$, with probability $1/4$; and so on. For base $b=2$, the decoded estimate is $2^C-1$. States $0,1,2,3,4$ represent estimates $0,1,3,7,15$. One stored increment covers an increasingly large interval of real arrivals.

This deep dive builds on approximate counting and sampling. The prerequisite chapter introduces the idea that randomized sampling can trade precision for space. Morris counting resolves a sharper question: how can the counter itself represent totals far larger than its numeric state, and why does the exponential decoder remain unbiased despite random skipped updates?

The algorithm maintains an integer state $C$, initially zero. For each unit-weight event, it increments $C$ with probability $b^{-C}$, where $b\gt1$. Its estimate is

$$ \widehat n(C)=\frac{b^C-1}{b-1}. $$

For $b=2$, suppose random draws for four arrivals are $0.40,0.70,0.10,0.30$. The first arrival certainly raises $C$ from 0 to 1. At $C=1$, the second draw $0.70$ misses the threshold $1/2$. The third draw $0.10$ succeeds and raises $C$ to 2. At $C=2$, the fourth draw $0.30$ misses the threshold $1/4$. The final state $C=2$ decodes to $3$, although four events occurred. A single realization need not be exact; unbiasedness concerns the average over the algorithm's randomness.

Important vocabulary follows from this mechanism. A probabilistic increment is the Bernoulli decision made per arrival. Exponential decoding maps the small state back to the count scale. An unbiased estimator has expectation equal to the true count, not zero error on every run. Variance measures spread across independent runs. Rescaling changes the base or combines several counters to trade state range, update work, and accuracy. Saturation occurs when the stored state reaches its largest representable value and can no longer advance correctly.

Why this matters is the double logarithm. After $n$ events, the typical state is about $\log_b n$. Storing a number of that magnitude takes about $\log_2\log_b n$ bits. A tiny state can therefore span enormous totals, although real implementations must also store randomness state, protect against overflow, and tolerate substantial estimator variance.

Exponential States and an Unbiased Decoder

Fix a base $b\gt1$. Let $C_t$ be the state after $t$ unit arrivals and define $Y_t=b^{C_t}$. Conditional on $C_t=c$, the next state is $c+1$ with probability $b^{-c}=1/Y_t$ and remains $c$ otherwise. If the increment happens, $Y_t$ is multiplied by $b$.

The decisive calculation conditions on the current state:

$$ \mathbb E[Y_{t+1}\mid Y_t] =\frac1{Y_t}(bY_t)+\left(1-\frac1{Y_t}\right)Y_t =Y_t+(b-1). $$

Taking total expectation removes the conditioning:

$$ \mathbb E[Y_{t+1}]=\mathbb E[Y_t]+(b-1). $$

Because $Y_0=b^0=1$, induction gives $\mathbb E[Y_t]=1+t(b-1)$. Therefore

$$ \widehat n_t=\frac{Y_t-1}{b-1}=\frac{b^{C_t}-1}{b-1} \quad\Longrightarrow\quad \mathbb E[\widehat n_t]=t. $$

Nothing was approximated in this proof. Its obligations are precise: unit arrivals; exact increment probability $b^{-C_t}$; fresh randomness with the required conditional distribution; initial state zero; matched update and decoder bases; no saturation; and arithmetic capable of representing or safely approximating the probability and decoded value.

The memory claim follows from scale. Since the decoded magnitude near state $C$ is about $b^C$, representing totals near $n$ needs $C=\Theta(\log_b n)$. An ordinary binary register storing $C$ therefore needs $\Theta(\log\log n)$ bits. This counts the counter state, not a random-number generator, metadata, replicated counters, or machine alignment.

A counterexample makes the correction visible. Reporting $b^C$ instead of $(b^C-1)/(b-1)$ has expectation $1+t(b-1)$, not $t$. For $b=2$, $2^C$ overestimates by one in expectation. An exact integer counter is the nearby alternative: it has zero variance and supports straightforward merge by addition, but requires $\Theta(\log n)$ state bits rather than $\Theta(\log\log n)$.

flowchart TD
    A[State C starts at zero] --> B[Define Y = b to power C]
    B --> C[Increment with probability 1 divided by Y]
    C --> D[On success Y becomes bY]
    D --> E[Conditional expected change is b minus 1]
    E --> F[Iterate expectation for t arrivals]
    F --> G[E of Y is 1 plus t times b minus 1]
    G --> H[Decode Y minus 1 over b minus 1]
    H --> I[Unbiased estimate of t]
    C --> X{Probability exact and unsaturated?}
    X -->|no| Y[Invariant breaks and bias appears]
    X -->|yes| D
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C navy;
    class D,E,F purple;
    class G,H,I teal;
    class X,Y crimson;

Variance, Rescaling and Counter Saturation

Unbiasedness does not imply concentration. To quantify noise, square the transformed state. Conditional on $Y_t$,

$$ \mathbb E[Y_{t+1}^2\mid Y_t] =Y_t^2+(b^2-1)Y_t. $$

Using $\mathbb E[Y_t]=1+t(b-1)$ and summing the recurrence gives

$$ \mathbb E[Y_t^2] =1+(b^2-1)\left[t+\frac{(b-1)t(t-1)}2\right]. $$

After subtracting $\mathbb E[Y_t]^2$ and dividing by $(b-1)^2$, the decoded estimator has

$$ \operatorname{Var}(\widehat n_t)=\frac{b-1}{2}t(t-1). $$

For large $t$, one counter's relative standard deviation approaches $\sqrt{(b-1)/2}$. Base two therefore approaches about $70.7\%$, much too noisy for many production metrics. Averaging $r$ independent counters preserves unbiasedness and divides variance by $r$; the relative standard deviation approaches $\sqrt{(b-1)/(2r)}$. Robust grouping and median amplification can convert a constant-probability accuracy statement into higher confidence, at additional memory and update cost.

Choosing $b$ closer to one lowers variance but pushes the state higher: $C\approx\log_b((b-1)n+1)$. This may require more state bits and causes more accepted increments. The base is therefore a three-way control over accuracy, state range, and update behavior.

Saturation is not harmless clipping. If the maximum state is $C_{\max}$, then once it is reached, the transition that underpins the expectation recurrence disappears. The estimator becomes capped at $(b^{C_{\max}}-1)/(b-1)$ and increasingly biased downward. Probability underflow can create an earlier effective saturation if $b^{-C}$ rounds to zero; decoder overflow can create an infinite or invalid result even while the state remains valid.

from math import sqrt
from random import Random

def decode(state, base):
    if base <= 1:
        raise ValueError("base must exceed one")
    if state < 0:
        raise ValueError("state must be nonnegative")
    return (base ** state - 1.0) / (base - 1.0)

def morris_count(events, base=2.0, seed=0, max_state=None):
    if not isinstance(events, int) or events < 0:
        raise ValueError("events must be a nonnegative integer")
    if base <= 1:
        raise ValueError("base must exceed one")
    rng = Random(seed)
    state = 0
    saturated = False
    for _ in range(events):
        if max_state is not None and state >= max_state:
            saturated = True
            continue
        if rng.random() < base ** (-state):
            state += 1
    return state, decode(state, base), saturated

def exact_moments(events, base=2.0, max_state=None):
    probabilities = [1.0]
    for _ in range(events):
        next_probabilities = [0.0] * (len(probabilities) + 1)
        for state, mass in enumerate(probabilities):
            if max_state is not None and state >= max_state:
                next_probabilities[state] += mass
                continue
            p = base ** (-state)
            next_probabilities[state] += mass * (1 - p)
            next_probabilities[state + 1] += mass * p
        probabilities = next_probabilities
    estimates = [decode(state, base) for state in range(len(probabilities))]
    mean = sum(p * value for p, value in zip(probabilities, estimates))
    variance = sum(p * (value - mean) ** 2
                   for p, value in zip(probabilities, estimates))
    return mean, variance

#Normal exact check against the derived formulas on a stable small instance.
exact_n, base = 100, 2.0
mean, variance = exact_moments(exact_n, base)
expected_variance = (base - 1) * exact_n * (exact_n - 1) / 2
print("exact mean / variance:", mean, variance)
assert abs(mean - exact_n) < 1e-9
assert abs(variance - expected_variance) < 1e-5

#Deterministic simulation checks scale without replacing the proof.
n = 1000
trials = 20_000
values = [morris_count(n, base, seed)[1] for seed in range(trials)]
sample_mean = sum(values) / trials
sample_variance = sum((x - sample_mean) ** 2 for x in values) / trials
print("simulation mean / relative sd:", sample_mean,
      sqrt(sample_variance) / sample_mean)
assert abs(sample_mean - n) < 25

#Boundary and adversarial cases.
assert morris_count(0, seed=7)[1] == 0
_, capped, saturated = morris_count(100_000, seed=7, max_state=8)
print("capped estimate / saturated:", capped, saturated)
assert saturated and capped <= 255
for bad_events, bad_base in [(-1, 2.0), (10, 1.0)]:
    try:
        morris_count(bad_events, bad_base)
    except ValueError as error:
        print("invalid test passed:", error)

Tiny Counters for Massive Event Totals

In a teaching setting, Morris counting makes expectation tangible. Students can trace a small random sequence, then derive why rare large jumps yield constant expected progress. Comparing one path with an exact state distribution prevents the common mistake of interpreting unbiasedness as pathwise accuracy.

At professional scale, imagine billions of low-value per-key diagnostic counters on constrained devices or in a dense telemetry table. Saving even a few bytes per key can matter. A tuned base and replicated counters may estimate large totals while using tiny state. The design must include a small-count policy, random-stream isolation, saturation telemetry, versioned base parameters, and empirical calibration against exact shadow counters.

The failure case is equally important. Billing, rate-limit enforcement, inventory, financial ledgers, and safety-event totals usually require exact or one-sided guarantees; an unbiased but highly variable counter is inappropriate. Adversaries may also exploit predictable random-number streams or send enough events to saturate state. Dropped events before the counter are not sampling noise and are not repaired by unbiased decoding.

Merging is subtle. Two independent Morris states cannot generally be added or decoded-and-added while retaining the distribution of a single counter over the combined stream. Safe distributed designs need a proven merge procedure, preserve sufficient replicated state, or aggregate exact/local counts before applying a counter at a defined boundary. “Both estimates are unbiased” only implies their numerical sum is an unbiased estimate of the sum; it does not make the summed state a valid Morris state for future updates.

Evidence that invalidates deployment includes sustained calibration bias, variance above the formula, cross-counter correlation, probability underflow, unexpected state saturation, incompatible base or RNG versions, failed merge invariants, and unacceptable error in decision-critical subgroups.

flowchart TD
    A[Define decision and tolerated error] --> B{Exact counter affordable?}
    B -->|yes| C[Use exact counter]
    B -->|no| D[Choose base state width and replicas]
    D --> E[Verify maximum decoded range]
    E --> F[Validate RNG independence and arithmetic]
    F --> G[Replay representative and hostile streams]
    G --> H{Bias variance and saturation acceptable?}
    H -->|no| I[Reject resize or use hybrid]
    H -->|yes| J[Deploy with exact shadow sample]
    J --> K[Monitor calibration correlation and state headroom]
    K --> L{Assumption or SLO breach?}
    L -->|yes| I
    L -->|no| K
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C navy;
    class D,E,F,G purple;
    class J,K teal;
    class H,I,L crimson;

Implement and Calibrate Morris Counting

Mastery combines an exact expectation proof with implementation skepticism. The recurrence is short, yet production correctness depends on event semantics, floating-point behavior, random streams, state width, and aggregation. A good implementation exposes these choices rather than hiding them behind a function named increment.

The conceptual bridge backward is Bernoulli sampling and conditional expectation. The bridge forward leads to probabilistic data structures, stochastic averaging, confidence amplification, mergeable summaries, and floating-point-like encodings. Morris counting is especially useful as a lesson in co-design: the state transition and decoder are mathematically inseparable.