Probabilistic Counting, in depth: Morris counters, Flajolet-Martin and PCSA, linear counting and KMV, and how to choose

Two different counting problems

There are two different questions hiding under the word counting, and they need different machinery.

• Event counting: how many times has something happened? Every arrival counts, including repeats. The Morris counter answers this.
• Distinct counting (cardinality): how many different items have we seen? Repeats must count once. Flajolet-Martin, PCSA, linear counting, KMV, LogLog and HyperLogLog answer this. All of them start by hashing each item, so a repeat produces the same hash and cannot change the state twice. That property, idempotence, is what makes these sketches mergeable across machines.

The Morris counter: counting events in log log n bits

Morris's idea: instead of storing n, store X, roughly log2 n, and increment X only occasionally. With X at its current value, an arrival increments it with probability 2^-X. The estimate is 2^X - 1.

Why is that unbiased? Let Y = 2^X. When an event arrives, Y doubles with probability 1/Y, so its expected increase is (1/Y) * Y = 1. Y starts at 1, so after n events E[Y] = n + 1 and E[2^X - 1] = n. The same style of argument gives Var = n(n-1)/2, a relative standard deviation of about 1/√2, or 71 percent. A single Morris counter is unbiased but very noisy, and it needs only log2 log2 n bits: five bits reach about two billion events.

Two standard fixes buy accuracy with bits. Averaging k independent counters divides the variance by k. Changing the base is usually cheaper: increment with probability (1+a)^-X and estimate ((1+a)^X - 1) / a. The variance becomes a * n(n-1)/2, so the relative error is about sqrt(a/2), and X grows like ln(a*n) / ln(1+a), so you pay a few more bits.

import random

class MorrisCounter:
    """Approximate event counter. a=1 is Morris's original base-2 counter."""
    def __init__(self, a=1.0, rng=random.random):
        self.a, self.x, self.rng = a, 0, rng

    def incr(self):
        if self.rng() < (1.0 + self.a) ** -self.x:
            self.x += 1

    def estimate(self):
        return ((1.0 + self.a) ** self.x - 1.0) / self.a

Worked example: you need per-key event counts up to a billion. An exact counter needs 30 bits.

At a = 1/64 you save almost two thirds of the space for under 9 percent error. That matters when the counters are the data structure: per-item popularity counters in a cache's eviction policy (Redis's LFU mode keeps an 8-bit probabilistic logarithmic counter per key, a close relative), per-flow counters in switch memory, or per-cell counters in a Count-Min sketch, where approximate counters shrink each cell. Do not use Morris counters for anything billed or audited.

Flajolet-Martin and PCSA

Flajolet and Martin turned to distinct counting with a simple observation about uniform hash values. Write each hash in binary and look at rho(y), the position of its lowest 1 bit, counting from 0. Half of all hashes have rho = 0, a quarter have rho = 1, an eighth have rho = 2. If you have seen n distinct items you expect to have seen rho values up to about log2 n, and duplicates do not matter because they hash identically.

The algorithm keeps a bitmap and sets BITMAP[rho(hash(x))] = 1 for each item. Let R be the index of the lowest bit still 0. Flajolet and Martin showed E[R] ≈ log2(φ n) with φ ≈ 0.77351, so the estimate is 2^R / φ. R is a better statistic than the maximum rho because it is less sensitive to one lucky hash, but a single bitmap still has a standard deviation of about 1.12 in R, which means the estimate is often off by a factor of two.

The fix is stochastic averaging, which gives PCSA (Probabilistic Counting with Stochastic Averaging). Use m bitmaps; the low bits of the hash pick which bitmap an item updates and the remaining bits feed rho. Average the m values of R and estimate (m / φ) * 2^(mean R). The standard error falls to about 0.78 / sqrt(m), and each item still costs one hash and one bit write.

import hashlib

PHI = 0.77351

def h64(item: bytes) -> int:
    return int.from_bytes(hashlib.blake2b(item, digest_size=8).digest(), "little")

def rho(y: int) -> int:                     # index of lowest set bit
    return (y & -y).bit_length() - 1 if y else 63

class PCSA:
    def __init__(self, m=1024):             # m must be a power of two
        self.m, self.shift = m, m.bit_length() - 1
        self.maps = [0] * m                 # one 32-bit bitmap per bucket

    def add(self, item: bytes):
        y = h64(item)
        j = y & (self.m - 1)                # bucket from low bits
        r = rho(y >> self.shift)            # rank from the rest
        if r < 32:
            self.maps[j] |= 1 << r

    def merge(self, other):                 # union of two streams
        self.maps = [a | b for a, b in zip(self.maps, other.maps)]

    def estimate(self):
        total = 0
        for bm in self.maps:
            r = 0
            while bm & (1 << r):
                r += 1                      # lowest zero bit
            total += r
        return self.m / PHI * 2 ** (total / self.m)

Merging two PCSA sketches is a bitwise OR per bitmap, which gives exactly the sketch of the union of the two streams, so shards can be counted separately and combined centrally without shipping identifiers. The weak spot is small cardinalities: when n is not much larger than m, many bitmaps are empty and the averaged estimate is biased upward. Production PCSA needs a small-range correction, which is exactly where linear counting comes in.

Linear counting

Linear counting, from Whang, Vander-Zanden and Taylor in 1990, uses a plain bitmap of m bits. Hash each item to one bit and set it. If V is the fraction of bits still zero, the estimate is n ≈ -m * ln(V). The reasoning is a balls-in-bins calculation: each of n distinct items misses a given bit with probability 1 - 1/m, so the expected fraction of empty bits is about e^(-n/m).

Its accuracy is excellent while the load t = n/m is moderate: the standard error is sqrt(m * (e^t - t - 1)) / n. At t = 1 with m = n = one million, that is about 0.085 percent from 125 KB. The catch is in the name: memory is linear in the cardinality you expect, and once V reaches zero the estimator is undefined. That makes it ideal for small ranges and as the low-end fallback inside PCSA and HyperLogLog, which both switch to it when many buckets are still empty.

K minimum values: a sketch that is also a sample

The k-minimum-values sketch looks at hash values as numbers instead of bit patterns. Map each item to a uniform value in (0, 1) and keep the k smallest distinct values. If n distinct values are spread uniformly, the k-th smallest, U_k, sits near k / n. The unbiased estimate is (k - 1) / U_k, with a relative standard error of about 1 / sqrt(k - 2).

import heapq

class KMV:
    def __init__(self, k=4096):
        self.k, self.heap, self.members = k, [], set()   # max-heap via negation

    def add(self, item: bytes):
        u = h64(item) / 2**64
        if u in self.members:
            return
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, -u); self.members.add(u)
        elif u < -self.heap[0]:
            self.members.discard(-heapq.heappushpop(self.heap, -u))
            self.members.add(u)

    def estimate(self):
        if len(self.heap) < self.k:
            return float(len(self.heap))                # exact below k
        return (self.k - 1) / -self.heap[0]

KMV costs more memory per unit of accuracy than PCSA or HyperLogLog, because it stores whole hash values. What it buys is a sample. The retained hashes are a uniform random sample of the distinct items, so you can estimate the Jaccard similarity of two sets, the size of their intersection, or the distinct count of a filtered subset by looking at which retained hashes satisfy a predicate. Theta sketches, as used in Apache DataSketches, generalise this idea and are the usual choice when you need set intersections and differences rather than only unions.

Choosing with arithmetic

Here is the decision in numbers. Target: 1 percent standard error on a distinct count of up to a billion.

The progression explains why HyperLogLog won the general-purpose slot. Flajolet and Martin used 32 bits per bucket to record a whole bitmap; LogLog kept only the maximum rho per bucket in five bits; HyperLogLog replaced LogLog's geometric mean with a harmonic mean, which damps outlier buckets and brings the constant from 1.30 to 1.04. PCSA is still worth knowing because its state is easy to reason about and audit, and KMV is worth knowing because it supports set operations. For the HLL estimator, sparse encoding and register layout, continue with HyperLogLog architecture, in depth.

Hashing is half the algorithm

Every distinct-count guarantee above assumes the hash behaves like a uniform random function on your data. Three practical consequences follow.

• Use a well-mixed 64-bit hash (xxHash64, MurmurHash3's 128-bit output truncated, BLAKE2b with an 8-byte digest). A 32-bit hash starts producing collisions that look like duplicates once you pass a few hundred million items.
• Never use a language's default object hash. Python's integers hash to themselves, so sequential user IDs produce rho values that reflect your ID scheme, not chance.
• Fix the hash function and seed across every producer whose sketches you will merge. Sketches built with different seeds merge into silent nonsense.

The theory behind the weaker independence that some of these estimators need is in Pairwise Independence, in depth; for a frequency sketch where approximate counters can shrink each cell, see Count-Min Sketch Architecture, in depth.

Failure modes

• Reporting an estimate as a fact. Showing 1,024,377 distinct users from a 1 percent sketch claims precision it does not have. Round, or show the interval.
• Small-range bias. PCSA and LogLog overestimate when most buckets are empty. Switch to linear counting below a threshold, or test the low end explicitly.
• Merging incompatible sketches. Different m, hash, or seed. Store these parameters with the serialized sketch and refuse to merge on mismatch.
• Treating a single Morris counter as accurate. 71 percent relative error surprises people. Use base (1+a) or averaging.
• Subtracting sketches. Union is exact on PCSA and HLL; difference and intersection via inclusion-exclusion amplify error badly when the intersection is small. Use KMV or theta sketches for set algebra.
• Adversarial input. If users control the items and know your hash, they can craft items with large rho values and inflate the count. Use a keyed hash when the input is untrusted.

Testing an implementation

Validate any implementation statistically, not with a single run. Generate streams of known cardinality, from 10 up to 10 million. For each n, build 200 sketches with different seeds and compute the bias (mean estimate over n, minus one) and the relative standard deviation. The standard deviation should match the formula for your sketch within roughly 10 percent, and the bias should be near zero across the whole range. A bias curve that bulges at small n is the missing small-range correction; a standard deviation consistently above the formula usually points at a weak hash.

import statistics

def check(make, n, trials=200):
    errs = []
    for seed in range(trials):
        s = make()
        for i in range(n):
            s.add(f"{seed}:{i}".encode())
        errs.append(s.estimate() / n - 1)
    return statistics.mean(errs), statistics.pstdev(errs)

# Expect bias near 0 and stdev near 0.78/sqrt(1024) = 0.024 for PCSA(1024)
print(check(lambda: PCSA(1024), 100_000))

What to do next

1. Write down which question you are answering: events or distinct items. The answer picks the family.
2. Choose the error you can tolerate and compute memory from the formula before writing code; use the comparison table above as a sanity check.
3. For per-key event counts at scale, prototype a base (1+a) Morris counter and measure its error against exact counts on a day of real traffic.
4. For distinct counts, default to HyperLogLog; pick KMV or theta sketches if you need intersections, and linear counting if the range is small and bounded.
5. Fix and record the hash, seed and size parameters with every serialized sketch, and reject merges on mismatch.
6. Run the bias and variance harness across several orders of magnitude before shipping.
7. Read HyperLogLog, in depth next for the estimator that replaced most of these in practice.