---
output-file: index.html
title: "Counting Distinct Elements in a Stream"
subtitle: "Notes 29 · Full lecture · 75 minutes"
author: "Sariel Har-Peled"
institute: "CS 574 · University of Illinois, Urbana-Champaign · Fall 2026"
---
## Two approaches to distinct counting
::: {.card-cyan}
First: the minimum of ideal random hash values.
Then: bounded samples using pairwise-independent randomness.
:::
::: {.card-green}
| Part | Minutes |
|:---|---:|
| Model and target | 5 |
| Minimum estimator and its moments | 20 |
| Pairwise sampling at one scale | 20 |
| Amplifying a mixed output | 10 |
| Unknown scale and finite seeds | 15 |
| Guarantees and discussion | 5 |
:::
::: {.notes}
Source: freq_est_2.tex, Chapter 29, with repairs in ../CORRECTIONS.txt.
Pacing includes board calculations and questions. All randomness is chosen
independently of the fixed input stream.
:::
## The object being counted
::: {.card-purple}
$$
\sigma=(s_1,\ldots,s_m),\quad s_t\in[n],\qquad
S=\{s_t:1\leq t\leq m\}.
$$
$$
u=|S|=F_0(\sigma).
$$
Repeated occurrences contribute only once to $S$.
:::
## The approximation guarantee
::: {.card-green}
Given $0<\varepsilon,\delta<1$, return $\widehat u$ such that
$$
\Pr[(1-\varepsilon)u\leq\widehat u\leq(1+\varepsilon)u]\geq1-\delta.
$$
:::
::: {.card-cyan}
One pass; insertion-only stream; space measured in words.
Return $0$ on an empty stream. For $n=1$, count exactly with a nonempty flag.
:::
## Randomness must be attached to values
::: {.card-purple}
A hash function $h$ assigns one random value to each key.
Every occurrence of key $i$ reuses $h(i)$.
:::
::: {.card-orange}
New randomness at every occurrence would reflect the stream length $m$.
The target here is the number $u$ of distinct values.
:::
## An ideal random function
::: {.card-cyan}
Assume $h:[n]\to[0,1]$ assigns independent uniform real values to distinct keys.
Store
$$
Y=\min_{1\leq t\leq m}h(s_t)=\min_{i\in S}h(i).
$$
:::
::: {.card-green}
The repeated values disappear automatically under the minimum operation.
:::
## First order statistic
::: {.card-purple}
For $u\geq1$, let
$$
X_1,\ldots,X_u\overset{\mathrm{iid}}\sim\operatorname{Unif}[0,1],
\qquad Y=\min(X_1,\ldots,X_u).
$$
:::
{fig-alt="Independent uniform hash values on the unit interval; the leftmost value is the stored minimum." width=1000}
## Compute the survival probability
::: {.card-green}
For $0\leq t\leq1$,
$$
\begin{aligned}
\Pr[Y>t]
&=\Pr[X_1>t,\ldots,X_u>t]\\
&=\prod_{i=1}^u\Pr[X_i>t]=(1-t)^u.
\end{aligned}
$$
:::
::: {.card-orange}
Independence is essential to the product.
:::
## From survival to density
::: {.card-cyan}
$$
F_Y(t)=\Pr[Y\leq t]=1-(1-t)^u.
$$
Differentiate on $(0,1)$:
$$
f_Y(t)=u(1-t)^{u-1}.
$$
:::
::: {.card-purple}
A density is not a point probability. For $0\leq a\leq b\leq1$,
$\Pr[a\leq Y\leq b]=\int_a^b f_Y(t)\,dt$.
:::
## Integrate the tail to get the mean
::: {.card-green}
Since $0\leq Y\leq1$,
$$
Y=\int_0^1\mathbf1[Y>t]\,dt.
$$
Taking expectations,
$$
\mathbb E Y=\int_0^1\Pr[Y>t]\,dt
=\int_0^1(1-t)^u\,dt=\frac1{u+1}.
$$
:::
## Compute the second moment
::: {.card-purple}
$$
Y^2=\int_0^1 2t\,\mathbf1[Y>t]\,dt.
$$
$$
\begin{aligned}
\mathbb E Y^2
&=2\int_0^1 t(1-t)^u\,dt\\
&=2\int_0^1(1-z)z^u\,dz\\
&=2\left(\frac1{u+1}-\frac1{u+2}\right)
=\frac2{(u+1)(u+2)}.
\end{aligned}
$$
:::
## Subtract the squared mean
::: {.card-cyan}
$$
\begin{aligned}
\operatorname{Var}(Y)
&=\frac2{(u+1)(u+2)}-\frac1{(u+1)^2}\\
&=\frac{u}{(u+1)^2(u+2)}.
\end{aligned}
$$
:::
::: {.card-green}
$$
\boxed{\frac{\operatorname{Var}(Y)}{(\mathbb E Y)^2}
=\frac{u}{u+2}<1.}
$$
:::
## What are we actually estimating?
::: {.card-orange}
$$
\mathbb E Y=\frac1{u+1},\qquad \mathbb E Y\neq u.
$$
First estimate $\mu=1/(u+1)$ accurately; then invert and subtract $1$.
:::
::: {.card-cyan}
The variance-to-mean-square ratio is bounded independently of $u$.
:::
## Recall the averaging step
::: {.card-purple}
For independent copies $Y_1,\ldots,Y_\alpha$, set
$$
A=\frac1\alpha\sum_jY_j.
$$
Then
$$
\mathbb E A=\mu,\qquad
\operatorname{Var}(A)\leq\frac{\mu^2}{\alpha}.
$$
:::
## Choose accuracy for the reciprocal
::: {.card-green}
Set $\eta=\varepsilon/4$ and $\alpha=\lceil64/\varepsilon^2\rceil$.
$$
\Pr[|A-\mu|>\eta\mu]
\leq\frac1{\alpha\eta^2}\leq\frac14.
$$
:::
::: {.card-cyan}
Each block needs $O(\varepsilon^{-2})$ independent minimum sketches.
:::
## Recall the median step
::: {.card-purple}
Build $\beta=2\lceil12\ln(1/\delta)\rceil+1$ independent block averages.
Let $Z=\operatorname{median}(A_1,\ldots,A_\beta)$.
:::
::: {.card-green}
If $G$ counts good blocks, then $\mathbb E G\geq3\beta/4$ and
$$
\Pr[|Z-\mu|>\eta\mu]
\leq\Pr[G<\beta/2]\leq e^{-\beta/24}\leq\delta.
$$
:::
## All sketches fit in one pass
::: {.card-cyan}
Choose independent ideal functions $h_{i,j}$. On item $s_t$, update
$$
Y_{i,j}\gets\min\{Y_{i,j},h_{i,j}(s_t)\}.
$$
At the end, average within blocks and take the median across blocks.
:::
::: {.card-purple}
$$
M=\alpha\beta=O\left(\varepsilon^{-2}\log\frac2\delta\right).
$$
:::
## Convert the estimate back to $u$
::: {.card-green}
On the success event, write
$$
Z=\frac{1+\theta}{u+1},\qquad |\theta|\leq\varepsilon/4.
$$
Output $\widehat u=1/Z-1$. Then
$$
\widehat u-u=-\frac{(u+1)\theta}{1+\theta}.
$$
:::
## Bound the reciprocal error
::: {.card-purple}
For $u\geq1$ and $0<\varepsilon<1$,
$$
\begin{aligned}
\frac{|\widehat u-u|}{u}
&=\frac{u+1}{u}\frac{|\theta|}{|1+\theta|}\\
&\leq\frac{2|\theta|}{1-|\theta|}
\leq\frac{2\varepsilon}{4-\varepsilon}<\varepsilon.
\end{aligned}
$$
:::
## The idealized theorem
::: {.card-green}
Assuming perfectly random real-valued hashes and their stored values cost $O(1)$ words,
$$
\Pr[|\widehat u-u|>\varepsilon u]\leq\delta,
$$
using $O(\varepsilon^{-2}\log(2/\delta))$ words in one pass.
:::
::: {.card-orange}
The constant-space hash assumption is idealized. We next give an explicit finite-seed construction.
:::
::: {.notes}
Reach this slide near minute 25. The order-statistic argument is valuable
even though its randomness model is too strong for the claimed implementation.
:::
## A sample of distinct values
::: {.card-purple}
For each $i\in[n]$, let $B_i\in\{0,1\}$, with
$$
\Pr[B_i=1]=p.
$$
Assume the bits are pairwise independent and reproducible from a small seed.
:::
::: {.card-cyan}
Retain the set $R=\{i\in S:B_i=1\}$.
:::
## The update rule
::: {.card-green}
On arrival of $s_t$, evaluate $B_{s_t}$.
If it is $1$, insert $s_t$ into a set $R$; duplicates do nothing.
:::
{fig-alt="A fixed keep-or-discard decision per distinct key; repetitions do not create extra sample entries." width=1000}
## The sample size is a sum of indicators
::: {.card-purple}
$$
X=|R|=\sum_{i\in S}B_i.
$$
By linearity,
$$
\mathbb E X=\sum_{i\in S}\mathbb E B_i=pu.
$$
:::
::: {.card-orange}
The sum runs over distinct values, not stream positions.
:::
## Pairwise independence is enough for variance
::: {.card-cyan}
For $i\neq j$,
$$
\operatorname{Cov}(B_i,B_j)=0.
$$
Therefore
$$
\operatorname{Var}(X)=\sum_{i\in S}\operatorname{Var}(B_i)
=up(1-p)\leq up.
$$
:::
## Rescale the sample count
::: {.card-green}
For $p>0$, let $\rho=X/p$. Then
$$
\mathbb E\rho=u,\qquad
\operatorname{Var}(\rho)=\frac{u(1-p)}p.
$$
:::
::: {.card-purple}
$$
\Pr[|\rho-u|>\varepsilon u]
\leq\frac{1-p}{\varepsilon^2pu}
\leq\frac1{\varepsilon^2pu}.
$$
:::
## Why introduce a scale?
::: {.card-orange}
Accurate sampling needs $pu$ on the order of $\varepsilon^{-2}$.
But $u$ is the unknown target.
:::
::: {.card-cyan}
First solve a promised problem: given a scale $N$ with $u>N/4$,
return an estimate or a valid declaration that $u>2N$.
:::
## A precise one-scale contract
::: {.card-green}
Given $0<\varepsilon<1/4$ and $u>N/4$, output one of:
1. The declaration **large**: $u>2N$.
2. A number $\rho\in[(1-\varepsilon)u,(1+\varepsilon)u]$.
The output is correct with probability at least $7/8$.
:::
::: {.card-purple}
Both output types can be correct when $u>2N$.
:::
## Set the probability and memory cap
::: {.card-cyan}
In the ideal sampling calculation, choose
$$
p=\min\left\{1,\frac{32}{N\varepsilon^2}\right\},
\qquad T=pN.
$$
Keep distinct sampled keys until $|R|>8T$.
:::
::: {.card-orange}
The minimum with $1$ is necessary at small scales.
:::
## The one-scale algorithm
::: {.card-purple}
1. Maintain the sampled set $R$.
2. If its size exceeds $8T$, output **large** and discard this copy's set.
3. If no overflow occurs, output $\rho=|R|/p$ at the end.
:::
::: {.card-green}
The maximum stored size is $\lfloor8T\rfloor+1=O(\varepsilon^{-2})$.
:::
## Analyze the exact branch first
::: {.card-cyan}
If $p=1$, then $N\leq32/\varepsilon^2$ and $R$ contains every distinct key seen.
:::
::: {.card-green}
No overflow: return $|R|=u$ exactly.
Overflow: more than $8N$ distinct keys appeared, so $u>8N>2N$.
Both outputs are correct deterministically.
:::
## Analyze the sampling branch
::: {.card-purple}
Suppose $p=32/(N\varepsilon^2)<1$ and $u>N/4$. Then
$$
pu>\frac{32}{N\varepsilon^2}\frac N4=\frac8{\varepsilon^2}.
$$
:::
::: {.card-green}
$$
\Pr[|X-pu|>\varepsilon pu]
\leq\frac{\operatorname{Var}(X)}{\varepsilon^2p^2u^2}
\leq\frac1{\varepsilon^2pu}<\frac18.
$$
:::
## Use one success event for both output types
::: {.card-cyan}
Let $X$ be the size of the final conceptual sample, even if storage stopped at overflow.
Define
$$
\mathcal G=\{|X-pu|\leq\varepsilon pu\}.
$$
Then $\Pr[\mathcal G]\geq7/8$.
:::
::: {.card-purple}
On $\mathcal G$, prove correctness separately for a number and for **large**.
:::
## A numerical output is accurate
::: {.card-green}
If there was no overflow, the stored set is the full conceptual sample.
On $\mathcal G$,
$$
(1-\varepsilon)pu\leq X\leq(1+\varepsilon)pu.
$$
Divide by $p$:
$$
(1-\varepsilon)u\leq\rho\leq(1+\varepsilon)u.
$$
:::
## An overflow declaration is valid
::: {.card-purple}
Samples grow monotonically, so overflow implies $X>8pN$.
On $\mathcal G$, $X\leq(1+\varepsilon)pu$. Thus
$$
u\geq\frac X{(1+\varepsilon)p}
>\frac{8N}{1+\varepsilon}>2N.
$$
:::
::: {.card-orange}
This is an unconditional success proof. We do not condition the probability bound on observing overflow.
:::
## One-scale lemma proved
::: {.card-green}
Under $u>N/4$, the capped sampler uses $O(\varepsilon^{-2})$ words
and returns a correct output with probability at least $7/8$.
:::
::: {.card-cyan}
Small scale: exact counting until overflow.
Larger scale: pairwise sampling, rescaling, and Chebyshev.
:::
::: {.notes}
Reach this point near minute 45. Ask why the proof uses the conceptual final
sample after an actual copy has stopped storing items.
:::
## Independent repetitions at one scale
::: {.card-purple}
Run $r$ independent copies, each with its own seed and bounded sampled set.
Each output is either a number or **large**.
:::
::: {.card-orange}
The amplification rule must handle both types of output.
:::
## Aggregate the mixed outputs
::: {.card-green}
1. If at least half the copies say **large**, return **large**.
2. Otherwise, return the median of the numerical outputs.
:::
::: {.card-cyan}
For the proof, we will ensure fewer than $r/4$ copies are incorrect.
:::
## Define a bad copy by its output
::: {.card-purple}
A copy is bad if it gives a false declaration or an inaccurate number.
$$
B=\sum_{j=1}^r\mathbf1[\text{copy }j\text{ is bad}],
\qquad \Pr[\text{copy }j\text{ bad}]\leq1/8.
$$
The indicators are independent across copies.
:::
## Bound the bad-copy tail
::: {.card-cyan}
Using Markov on $2^B$,
$$
\Pr[B\geq r/4]\leq2^{-r/4}\mathbb E[2^B]
\leq\left(\frac{9/8}{2^{1/4}}\right)^r.
$$
Since $\ln(9/8)-(\ln2)/4<-1/24$,
$$
\Pr[B\geq r/4]\leq e^{-r/24}.
$$
:::
::: {.notes}
This elementary exponential-moment calculation is a concrete Chernoff bound.
It avoids applying full-independence tails to the pairwise bits within a copy.
:::
## A majority declaration contains a correct witness
::: {.card-green}
Suppose $B2N.
$$
So the aggregate declaration is correct.
:::
## The numerical median has a good majority
::: {.card-purple}
Otherwise, the number $q$ of numerical outputs satisfies $q>r/2$.
At most $BN/4$,
$$
p'u\geq p_0u>8/\varepsilon^2.
$$
Therefore the same Chebyshev bound applies.
:::
::: {.card-cyan}
If $p'=1$, the sample is exact. Its size is still capped, so the exact/overflow proof applies.
:::
## Rounding preserves the space bound
::: {.card-purple}
For $p_0<1$,
$$
T=p'N\leq\frac{32}{\varepsilon^2}+\frac NQ.
$$
At the dyadic scales used below, $N<2n$ and $Q\geq n$, so
$$
T<\frac{32}{\varepsilon^2}+2.
$$
:::
::: {.card-green}
The sample cap is $O(\varepsilon^{-2})$; the seed and threshold use $O(1)$ words.
:::
## Cover the possible scales
::: {.card-cyan}
For $n\geq2$, define
$$
L=\lceil\log_2 n\rceil,\qquad N_i=2^i\quad(1\leq i\leq L).
$$
Run an amplified sampler at every scale in parallel.
:::
{fig-alt="Dyadic scales increasing from 2 to at least n; the first scale at least u is the proof witness." width=1000}
## Share the failure budget across levels
::: {.card-purple}
Give each level failure budget $\eta=\delta/L$.
Its space is
$$
O\left(\varepsilon^{-2}\log\frac{2L}{\delta}\right).
$$
:::
::: {.card-green}
Across all $L$ levels:
$$
O\left(\varepsilon^{-2}L\log\frac{2L}{\delta}\right)\text{ words}.
$$
:::
## Select the first numerical output
::: {.card-cyan}
After the stream ends, inspect levels in increasing order.
Skip **large** declarations and return the first number.
:::
::: {.card-orange}
We must prove that a numerical output exists before leaving the range where the one-scale promise holds.
:::
## Choose a witness level for the proof
::: {.card-purple}
For $u\geq1$, let
$$
i_* = \min\{i:N_i\geq u\}.
$$
This exists since $N_L\geq n\geq u$.
$$
u\leq N_{i_*}\leq2u.
$$
:::
::: {.notes}
When u=1, the first level is N_1=2 and equality holds in the upper bound.
For u>1, minimality of the dyadic witness gives the stronger N_{i_*}<2u.
:::
## Every earlier level satisfies its promise
::: {.card-green}
For every $j\leq i_*$,
$$
N_j\leq N_{i_*}\leq2u,
\qquad N_j/4\leq u/22N_{i_*}\text{ is false}.
$$
It must return an accurate number. Any earlier number is also accurate.
:::
## Complete the scale-selection proof
::: {.card-purple}
The first numerical output occurs at some $j\leq i_*$.
On the simultaneous success event,
$$
(1-\varepsilon)u\leq\widehat u\leq(1+\varepsilon)u.
$$
Hence
$$
\Pr[|\widehat u-u|>\varepsilon u]\leq\delta.
$$
:::
::: {.notes}
On the failure event, all levels might declare large; define a fallback
output of zero in that case. It does not change the probability guarantee.
Reach this point near minute 70.
:::
## Distinct-count theorem with finite seeds
::: {.card-green}
For $n\geq2$, $0<\varepsilon<1/4$, and $0<\delta<1$, a one-pass algorithm uses
$$
O\left(\varepsilon^{-2}\log n\,
\log\frac{2\lceil\log_2 n\rceil}{\delta}\right)\text{ words}
$$
and returns a $(1\pm\varepsilon)$ estimate of $F_0$ with probability at least $1-\delta$.
:::
::: {.card-cyan}
Use exact handling for the empty stream and for $n=1$.
For larger requested $\varepsilon$, run with $\min\{\varepsilon,1/8\}$.
:::
## The high-probability form in the notes
::: {.card-purple}
Fix any constant $a>0$ and take $\delta=n^{-a}$. Then
$$
L=O(\log n),\qquad
\log(2L/\delta)=O(\log n).
$$
:::
::: {.card-green}
$$
\boxed{O(\varepsilon^{-2}\log^2n)\text{ words},
\qquad\Pr[\text{success}]\geq1-n^{-a}.}
$$
:::
## Keep the two randomness models distinct
::: {.card-cyan}
| Method | Randomness | Space |
|:---|:---|:---|
| Minimum + average + median | Ideal fully random real hashes | $O(\varepsilon^{-2}\log(2/\delta))$ ideal words |
| Capped sampling at dyadic scales | Finite pairwise hash seeds | $O(\varepsilon^{-2}L\log(2L/\delta))$ words |
:::
::: {.card-purple}
Both ignore repeated keys consistently; the second has an explicit small seed.
:::
## Reconstruct the argument
::: {.card-green}
1. Why does a minimum estimate $1/(u+1)$?
2. Why is pairwise independence enough for the sampling bound?
3. Why does amplification use fewer than a quarter bad copies?
4. Which scale ensures that the first numerical answer is trustworthy?
:::
::: {.notes}
Use the remaining discussion time. Answers: the survival probability;
variance uses only covariances; the numerical subset must still have a good
majority; the first dyadic scale at least u.
:::
## Source and references {.small}
::: {.card-purple}
Based on Notes 29, *Approximating the Number of Distinct Elements in a Stream*.
Prerequisites: median estimation from Notes 28, Chebyshev's inequality,
Chernoff amplification, and polynomial hashing. Background cited in the notes: [@mr-ra-95].
:::
::: {#refs}
:::