Morris Approximate Counting
An exact counter increments after every event.
Morris counting instead increments a counter c with probability and estimates the number of events by [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 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).
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:
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 .
Incrementing c doubles it to , while leaving c unchanged keeps it at .
The expected value after the event is
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.
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β
-
Morris (1978). Counting Large Numbers of Events in Small Registers.
Introduces approximate counting with small registers.
-
Nelson and Yu (2022). Optimal Bounds for Approximate Counting.
Section 1.2 describes the base-two counter and its expected value and variance.
(Section 1.2)