Approximate Counting & Stream Sampling

Counting Giants with Tiny State

Imagine a concert entrance with millions of arrivals but room for only a tiny notebook. One question is “roughly how many arrived?” Another is “which arrivals should we inspect later?” A compact counter addresses the first; a sample of records addresses the second. Both give up information, but in different ways. A count cannot reconstruct visitor attributes, and a few saved visitors cannot automatically give an accurate answer about a very rare group.

If four people arrive, an exact tally ends at $4$. A deliberately small randomized counter might instead finish with a value whose decoded estimate is $3$ or $7$; a guarantee describes its behavior over the counter's random choices, not that one run equals four. For sampling, suppose we keep one uniformly selected arrival from a four-person stream. Each person must have final selection probability $1/4$, even though the first person was once certain to be held. This is why an update rule needs a proof.

The preceding chapters introduced stream models, probability bounds, and controlled randomness. Here those tools answer three questions: What statistic is estimated? Which individual records can enter the sample, and with what probability? Which operations, such as merging workers or deleting events, preserve the stated guarantee? We start with insert-only streams of individually identified arrivals unless a different model is stated.

Counters, Samples and Inclusion Probabilities

Morris counting. Start an integer state $C=0$. On each insert-only arrival, increment $C$ with probability $2^{-C}$; otherwise leave it unchanged. Decode with $\widehat N=2^C-1$. The state increases rarely when it is large, using roughly $\log_2 N$ possible state values, or about $\log_2\log_2 N$ bits to represent the state at scale $N$ (ignoring fixed machine ranges and random-bit costs). The decoded answer is random and may be far from the true count in one run. It is an estimate of the number of processed insertions, not of distinct keys or the current total after arbitrary deletions.

Bernoulli sampling. For a fixed stream of $N$ records, independently retain record $i$ with probability $p_i$ known in advance or recorded when chosen. If all probabilities equal $p$, the retained count $S$ has expectation $Np$ and $S/p$ is unbiased for $N$. The sample size varies. For a property $y_i$, the inverse-probability estimator $\widehat T=\sum_{i\text{ retained}}y_i/p_i$ has expectation $T=\sum_i y_i$ when each $p_i>0$ and the decisions have those marginals. Independence is not needed for that expectation, but it affects variance. A changed or unknown selection probability invalidates the weighting argument.

Reservoir sampling. Hold the first $k$ arrivals. For arrival $t>k$, accept it with probability $k/t$ and, if accepted, replace a uniformly chosen held item. At time $t\ge k$, each arrival has inclusion probability $k/t$, and the held set is a uniform size-$k$ subset of the first $t$ distinct arrival positions. This is without replacement over positions. It does not sample unique values uniformly when duplicates arrive.

Bottom-$k$ and weighted priority. Give each unique record ID an independently uniform continuous rank in $(0,1)$ and keep the $k$ smallest ranks; for a fixed population, this gives a uniform subset of size $k$ with probability $k/N$ per item. Deterministic seeded hash ranks approximate this ideal only to the extent their proven independence or min-wise properties justify it; ties need a stable rule. For positive item weights $w_i$, an ideal weighted priority can use an independent uniform $U_i$ and score $E_i=-\ln(U_i)/w_i$, retaining small scores. The first selected item has probability $w_i/\sum_jw_j$. For a multi-item weighted sample, inclusion probabilities depend on the procedure and other weights; they are not generally $kw_i/\sum_jw_j$. These are distinct sampling contracts, not interchangeable variants.

flowchart TD
    A["Insert-only arrival positions"] --> Q{"Which output?"}
    Q -->|Volume| M["Morris state C"]
    M --> N["Estimate 2^C minus 1"]
    Q -->|Independent records| B["Bernoulli decisions"]
    B --> P["Known inclusion probabilities"]
    Q -->|Fixed number of records| R["Reservoir or bottom-k"]
    R --> U["Uniform subset if assumptions hold"]
    Q -->|Weight-biased selection| W["Exponential priorities"]
    W --> V["Weight-specific inclusion analysis"]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class A,Q navy; class M,N,B,P teal; class R,U purple; class W,V crimson;

Unbiased Estimates, Variance and Merge Rules

The Morris estimator's unbiasedness follows from one conditional step. At state $C$, an increment changes $2^C$ by $2^C$; it occurs with probability $2^{-C}$. Hence the conditional expected change in $2^C-1$ is exactly $1$. Starting at zero, $\mathbb E[\widehat N]=N$ after $N$ insertions. The variance quantifies why this alone is a weak per-run promise. Let $A_N=\mathbb E[2^{C_N}]$ and $B_N=\mathbb E[4^{C_N}]$. The update gives $A_N=N+1$ and $B_{N+1}-B_N=3A_N$. Summing yields $B_N=1+3N(N+1)/2$ and therefore $\operatorname{Var}(\widehat N)=N(N-1)/2$. Relative standard deviation approaches $1/\sqrt2$, so achieving small relative error needs a modified counter design or independent replicas and a justified aggregation rule.

For equal-probability Bernoulli sampling, write $S=\sum_{i=1}^N I_i$ with independent indicators of mean $p$. Then $\mathbb E[S/p]=N$ and $\operatorname{Var}(S/p)=N(1-p)/p$. A property total $T$ can be estimated by weighting observed values by reciprocal inclusion probability; its variance depends on joint inclusion probabilities when sampling decisions are dependent. For a fixed-size reservoir, the naive sample fraction is unbiased for a population fraction, while an observed count without scaling is generally not an estimate of the full count.

To prove the reservoir invariant, the new position is included with probability $k/t$. Any older position held at step $t-1$ survives step $t$ with probability $1-(k/t)(1/k)=1-1/t$. By induction its final inclusion probability is $(k/(t-1))((t-1)/t)=k/t$. To prove the stronger uniform subset claim, consider a particular size-$k$ subset: if it excludes the new item, the previous same subset must survive; if it includes the new item, one of its $k$ possible predecessor subsets must replace the correct old position. Both cases give probability $1/\binom tk$.

Merging needs a separate theorem. Independently generated Morris states cannot simply be added: $C_A+C_B$ decodes to $(2^{C_A+C_B}-1)$, generally unrelated to $N_A+N_B$. Two one-slot uniform reservoirs from shards of sizes $n_A,n_B$ can be merged by choosing shard A's held item with probability $n_A/(n_A+n_B)$ and B's otherwise; the result is uniform over the union of arrival positions. For larger reservoirs, a merge needs a size-aware procedure. Bottom-$k$ can retain the $k$ smallest ranks from the union of local bottom-$k$ lists if every worker uses consistent ranks for the same unique IDs and the population/duplicate policy is explicit. Distinct worker seeds or mismatched key encodings break that identity.

flowchart TD
    A["Choose target and sampling unit"] --> C{"Which estimator?"}
    C -->|Morris| M["Conditional mean increment = 1"]
    M --> V["Compute variance; unbiased is not precise"]
    C -->|Reservoir| R["New item k/t; old survives 1−1/t"]
    R --> U["Uniform subset by induction"]
    C -->|Bernoulli| B["Known inclusion probabilities"]
    B --> H["Inverse-probability total"]
    V --> G{"Need to merge shards?"}
    U --> G
    H --> G
    G --> D["Use a method-specific merge proof"]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class A,C navy; class M,R,B,U,H teal; class V,D crimson; class G purple;

Traffic Sampling, Reservoirs and Rare Events

Approachable audit. A school receives six anonymous survey cards in arrival order and wants to inspect two. A two-slot reservoir gives each card probability $2/6=1/3$ of inclusion. If the first four cards happen to report a positive experience and the last two a negative one, keeping the first two would systematically conceal the negatives; a uniform reservoir does not. But after any single realization, two cards remain too few for a strong conclusion about a rare complaint rate. The formal population is cards, not students, if one student may submit several cards.

Production network telemetry. Suppose a gateway processes $100{,}000$ requests per second and retains each request independently with probability $p=0.001$. Expected retention is $100$ records per second, and each retained request can represent $1{,}000$ requests in an inverse-probability total. Over one second, the count estimator has variance $N(1-p)/p\approx99{,}900{,}000$, giving standard deviation about $9{,}995$ around $N=100{,}000$. These are stylized fixed-rate calculations; drops before the sampler, bursts, retention capacity, user-level correlations, and privacy rules require separate treatment. A fixed-size reservoir helps bound stored record count; Bernoulli sampling gives independent decisions and simpler scaling but variable output volume.

Rare and adversarial events. If an event type has true fraction $q=10^{-5}$ among requests, retaining each request with probability $p=0.001$ yields an expected $Np q$ rare retained events. Over $N=100{,}000$ requests, that is $0.001$; under independent selection and a fixed population with exactly one rare event, the chance of capturing it is only $0.001$. Weighting a retained rare event by $1/p$ does not make it likely to be retained. An attacker who changes event volume or chooses IDs after learning a seeded bottom-$k$ ranking may invalidate a fixed-stream guarantee. Rare-event monitoring needs stratification, targeted collection, or another explicit design, with new inclusion probabilities and threat assumptions.

Design a Memory-Bounded Measurement Plan

Begin with the unit and statistic, then select a mechanism whose probability statement answers that question. Check the representation cost of a counter or retained records, the randomness source, and how the result is updated and merged. The exercises below progress from a simple trace to a production decision with falsifiable criteria.