Skip to main content

Morris Approximate Counting

An exact counter increments after every event. Morris counting instead increments a counter c with probability 2βˆ’c2^{-c} and estimates the number of events by 2cβˆ’12^c-1 [Morris 1978]. As the counter grows, increments become rarer and represent larger changes to the estimate.

How does a counter that often ignores an event still track the number of events in expectation? We verify that after n events, the expected estimate is at most n.

The Program​

The function exp2(c) represents 2c2^c using the domain axioms explained below. The variable remaining counts the events still to process. Each iteration processes one event and increments c with probability 1/exp2(c).

Morris counting and its expected-value upper bound
Expected: Verified
@wp coproc morris(n: UInt) -> (c: UInt)
pre n + 1
post exp2(c)
{
c = 0
var remaining: UInt = n

@invariant(exp2(c) + remaining)
while remaining > 0 {
var increment: Bool = flip(1/exp2(c))
if increment { c = c + 1 } else {}
remaining = remaining - 1
}
}

The @wp coproc specification bounds the expected final value of exp2(c) by n + 1. The loop terminates after exactly n iterations because remaining decreases from n to zero. Subtracting one gives the stated bound on the estimate:

E(2cβˆ’1)≀n.\mathbb{E}(2^c-1)\le n.

The proof covers every unsigned input n, including zero.

Why the Invariant Works​

The @invariant annotation uses exp2(c) + remaining. The first term is the current estimate plus one, and the second allows an expected increase of one for each remaining event.

Suppose the current value of exp2(c) is z=2cz=2^c. Incrementing c doubles it to 2β‹…z2\cdot z, while leaving c unchanged keeps it at zz. The expected value after the event is

1zβ‹…2β‹…z+(1βˆ’1z)β‹…z=z+1.\frac1z\cdot2\cdot z+\left(1-\frac1z\right)\cdot z=z+1.

At the same time, remaining decreases by one, preserving the invariant in expectation. Initially exp2(0) == 1, giving n + 1. At exit, remaining == 0, leaving the postexpectation exp2(c).

Axioms for Exponentiation​

The domain declaration supplies the equations needed to relate the state-dependent probability to the change in the estimate.

Exponentiation axioms
domain Exponentials {
func exp2(c: UInt): UReal
axiom exp2_base exp2(0) == 1
axiom exp2_step forall c: UInt. exp2(c + 1) == 2 * exp2(c)
axiom exp2_at_least_one forall c: UInt. exp2(c) >= 1
}

The base and recurrence equations describe powers of two on natural exponents. The additional axiom exp2(c) >= 1 lets the solver establish that 1/exp2(c) lies between zero and one. These axioms hold for the intended interpretation exp2(c) = 2^c.

The verified specification establishes an upper bound on the expected estimate. For the algorithm's exact mean, variance, and space analysis, see the literature [Nelson and Yu 2022, Β§1.2].

See Also​

  • Reservoir Sampling samples one stream position uniformly using a state-dependent replacement probability.
  • Coupon Collector combines user-defined functions with an invariant for the expected number of draws.

References​