---
output-file: index.html
title: "Counting Distinct Elements in a Stream"
subtitle: "Notes 29 · Mathematical summary"
author: "Sariel Har-Peled"
institute: "CS 574 · University of Illinois, Urbana-Champaign · Fall 2026"
---

## Model and guarantee

::: {.card-cyan}
$$
\sigma=(s_1,\ldots,s_m)\in[n]^m,\quad S=\{s_t:1\leq t\leq m\},\quad u=|S|=F_0.
$$
$$
\Pr[|\widehat u-u|>\varepsilon u]\leq\delta.
$$
:::

::: {.card-purple}
One insertion-only pass; words store keys, counts, and hash seeds.
Empty stream $\mapsto0$; $n=1$ handled exactly.
:::

## Minimum of independent uniforms

::: {.card-green}
$$
X_1,\ldots,X_u\overset{\mathrm{iid}}\sim\operatorname{Unif}[0,1],
\qquad Y=\min_iX_i,\quad u\geq1.
$$
For $0\leq t\leq1$,
$$
\Pr[Y>t]=\prod_i\Pr[X_i>t]=(1-t)^u.
$$
$$
F_Y(t)=1-(1-t)^u,\qquad f_Y(t)=u(1-t)^{u-1}\quad(0<t<1).
$$
:::

## Moments of the minimum

::: {.card-cyan}
$$
\mathbb E Y=\int_0^1(1-t)^u\,dt=\frac1{u+1}.
$$
$$
\mathbb E Y^2=2\int_0^1t(1-t)^u\,dt
=2\left(\frac1{u+1}-\frac1{u+2}\right)
=\frac2{(u+1)(u+2)}.
$$
:::

::: {.card-purple}
$$
\operatorname{Var}(Y)=\frac{u}{(u+1)^2(u+2)},\qquad
\frac{\operatorname{Var}(Y)}{(\mathbb E Y)^2}=\frac{u}{u+2}<1.
$$
:::

## Ideal minimum sketch and amplification

::: {.card-green}
Fully random $h:[n]\to[0,1]$:
$$
Y=\min_t h(s_t)=\min_{i\in S}h(i),\qquad\mu=\frac1{u+1}.
$$
Independent copies; $\alpha=\lceil64/\varepsilon^2\rceil$ per average:
$$
\Pr[|A-\mu|>(\varepsilon/4)\mu]\leq\frac{16}{\alpha\varepsilon^2}\leq\frac14.
$$
:::

::: {.card-cyan}
$\beta=2\lceil12\ln(1/\delta)\rceil+1$ blocks; $Z=\operatorname{median}(A_i)$:
$$
\Pr[|Z-\mu|>(\varepsilon/4)\mu]\leq e^{-\beta/24}\leq\delta.
$$
:::

## Reciprocal conversion

::: {.card-purple}
On success, $Z=(1+\theta)/(u+1)$, $|\theta|\leq\varepsilon/4$.
$$
\widehat u=\frac1Z-1,\qquad
\frac{|\widehat u-u|}{u}
=\frac{u+1}{u}\frac{|\theta|}{|1+\theta|}
\leq\frac{2\varepsilon}{4-\varepsilon}<\varepsilon.
$$
:::

::: {.card-green}
$$
\Pr[|\widehat u-u|>\varepsilon u]\leq\delta,\qquad
O\left(\varepsilon^{-2}\log\frac2\delta\right)\text{ ideal words}.
$$
Assumption: each perfectly random real hash and stored value costs $O(1)$ words.
:::

## Pairwise sampling of distinct values

::: {.card-cyan}
Pairwise-independent bits: $\Pr[B_i=1]=p$.
$$
R=\{i\in S:B_i=1\},\qquad X=|R|=\sum_{i\in S}B_i.
$$
Insert a key only when its fixed bit is $1$; store it only once.
:::

::: {.card-green}
$$
\mathbb E X=pu,\qquad
\operatorname{Var}(X)=\sum_{i\in S}p(1-p)=pu(1-p).
$$
$$
\Pr[|X/p-u|>\varepsilon u]\leq\frac{1-p}{\varepsilon^2pu}.
$$
:::

## Capped estimator at scale $N$

::: {.card-purple}
Promise: $u>N/4$, $0<\varepsilon<1/4$.
$$
p=\min\{1,32/(N\varepsilon^2)\},\qquad T=pN.
$$
If $|R|>8T$, stop this copy and return **large** ($u>2N$).
Otherwise return $\rho=|R|/p$ at end.
:::

::: {.card-green}
$$
|R|\leq\lfloor8T\rfloor+1=O(\varepsilon^{-2}).
$$
For $p=1$: no overflow $\Rightarrow\rho=u$; overflow $\Rightarrow u>8N>2N$.
:::

## One-scale concentration

::: {.card-cyan}
For $p<1$, $pu>8/\varepsilon^2$. Let $X$ be the final conceptual sample size.
$$
\mathcal G=\{|X-pu|\leq\varepsilon pu\},\qquad
\Pr[\mathcal G^c]\leq\frac1{\varepsilon^2pu}<\frac18.
$$
:::

::: {.card-purple}
On $\mathcal G$:
$$
\begin{aligned}
\text{no overflow}&\ \Longrightarrow\ |\rho-u|\leq\varepsilon u;\\
\text{overflow}&\ \Longrightarrow\ X>8pN
\ \Longrightarrow\ u>8N/(1+\varepsilon)>2N.
\end{aligned}
$$
:::

## Amplification with mixed outputs

::: {.card-green}
Run $r$ independent copies.

At least $r/2$ declarations $\Rightarrow$ return **large**.

Otherwise $\Rightarrow$ median of the numerical outputs.
:::

::: {.card-cyan}
Let $B$ count incorrect copies; $\Pr[\text{copy bad}]\leq1/8$.
$$
\Pr[B\geq r/4]\leq2^{-r/4}\mathbb E2^B
\leq\left(\frac{9/8}{2^{1/4}}\right)^r\leq e^{-r/24}.
$$
:::

## Proof of mixed-output aggregation

::: {.card-purple}
On $B<r/4$:

Declaration majority: at least $r/2$ declarations, so some declaration is correct.

Numerical majority: $q>r/2$ numbers and fewer than $r/4<q/2$ bad numbers; their median is accurate.
:::

::: {.card-green}
$$
r=\lceil24\ln(2/\eta)\rceil\quad\Longrightarrow\quad
\Pr[\text{incorrect output}]\leq\eta.
$$
$$
\text{space }O\left(\varepsilon^{-2}\log\frac2\eta\right),\qquad u>N/4.
$$
:::

## Finite pairwise-independent hash

::: {.card-cyan}
$n\geq2$; prime $n\leq Q<2n$; independent uniform $a,b\in\mathbb F_Q$.
$$
h(i)=a(i-1)+b\pmod Q.
$$
For $i\neq j$ and any $x,y$, the equations $h(i)=x,h(j)=y$ uniquely determine $(a,b)$.
$$
\Pr[h(i)=x,h(j)=y]=Q^{-2}.
$$
:::

::: {.card-purple}
Seed $(a,b)$: $O(\log n)$ bits; new independent seed for each repetition.
:::

## Actual sampling probability

::: {.card-green}
$$
p_0=\min\{1,32/(N\varepsilon^2)\},\quad K=\lceil Qp_0\rceil,
\quad B_i=\mathbf1[h(i)<K].
$$
$$
p'=K/Q\geq p_0,\qquad T=p'N,\qquad\rho=|R|/p'.
$$
:::

::: {.card-cyan}
If $p_0<1$ and $N<2n$,
$$
p'u\geq p_0u>8/\varepsilon^2,\qquad
T\leq32/\varepsilon^2+N/Q<32/\varepsilon^2+2.
$$
If $p'=1$, sampling is exact. The cap remains $O(\varepsilon^{-2})$.
:::

## Dyadic scales

::: {.card-purple}
$$
L=\lceil\log_2 n\rceil,\qquad N_i=2^i\quad(1\leq i\leq L).
$$
Run the amplified sampler at each level with failure budget $\eta=\delta/L$.
Return the first numerical output; if none exists, return $0$.
:::

::: {.card-green}
$$
\text{total space }O\left(\varepsilon^{-2}L\log\frac{2L}{\delta}\right).
$$
:::

## Witness level

::: {.card-cyan}
For $u\geq1$,
$$
i_*=\min\{i:N_i\geq u\},\qquad u\leq N_{i_*}\leq2u.
$$
For every $j\leq i_*$,
$$
N_j/4\leq N_{i_*}/4\leq u/2<u.
$$
:::

::: {.card-purple}
All levels through $i_*$ satisfy the one-scale promise.
:::

## First numerical output: correctness

::: {.card-green}
$$
\Pr[\exists j\leq i_*:\text{level }j\text{ incorrect}]
\leq i_*\delta/L\leq\delta.
$$
On simultaneous success:

$u\leq N_{i_*}$ rules out a correct **large** declaration at $i_*$.

Thus a number occurs by $i_*$, and every earlier numerical output is accurate.
:::

::: {.card-cyan}
$$
\Pr[|\widehat u-u|>\varepsilon u]\leq\delta.
$$
:::

## Finite-seed theorem

::: {.card-purple}
For $n\geq2$, $0<\varepsilon<1/4$, $0<\delta<1$:
$$
\Pr[(1-\varepsilon)F_0\leq\widehat u\leq(1+\varepsilon)F_0]\geq1-\delta.
$$
$$
\boxed{\text{one pass; }
O\left(\varepsilon^{-2}\log n\,
\log\frac{2\lceil\log_2n\rceil}{\delta}\right)\text{ words}.}
$$
:::

::: {.card-cyan}
Empty stream and $n=1$: exact. For larger requested $\varepsilon$, use $\min\{\varepsilon,1/8\}$.
:::

## High-probability corollary

::: {.card-green}
Fix $a>0$; take $\delta=n^{-a}$. Then
$$
\log(2L/\delta)=O(\log n),\qquad
\boxed{\text{space }O(\varepsilon^{-2}\log^2n)}.
$$
$$
\Pr[(1-\varepsilon)F_0\leq\widehat u\leq(1+\varepsilon)F_0]\geq1-n^{-a}.
$$
:::

## Sources {.small}

Notes 29, *Approximating the Number of Distinct Elements in a Stream*.
Prerequisites: median amplification, Chebyshev, Chernoff, and polynomial hashing.
Background cited by the notes: [@mr-ra-95].

::: {#refs}
:::