---
output-file: index.html
title: "Frequency Estimation over a Stream"
subtitle: "Notes 28 · Mathematical summary"
author: "Sariel Har-Peled"
institute: "CS 574 · University of Illinois, Urbana-Champaign · Fall 2026"
---

## Model and moments

::: {.card-cyan}
$$
\sigma=(s_1,\ldots,s_m)\in[n]^m,\qquad
f_i=|\{t:s_t=i\}|,\qquad F_k=\sum_{i=1}^n f_i^k.
$$
$$
F_0=|\{i:f_i>0\}|,\quad F_1=m,\quad F_\infty=\max_i f_i.
$$
:::

::: {.card-green}
Fixed integer $k\geq1$; $0<\varepsilon,\delta<1$; one insertion-only pass.
$$
\Pr[|\widehat F_k-F_k|>\varepsilon F_k]\leq\delta.
$$
Word model: $O(\log(n+1)+\log(m+1))$ bits; empty stream $\mapsto0$.
:::

## Averaging lemma

::: {.card-purple}
Independent $X_j$ with $\mathbb E X_j=\mu>0$, $\operatorname{Var}(X_j)=\nu<\infty$.
$$
\alpha=\max\{1,\lceil4\nu/(\varepsilon^2\mu^2)\rceil\},
\qquad A=\alpha^{-1}\sum_{j=1}^\alpha X_j.
$$
:::

::: {.card-green}
$$
\mathbb E A=\mu,\qquad\operatorname{Var}(A)=\nu/\alpha.
$$
$$
\Pr[|A-\mu|\geq\varepsilon\mu]
\leq\frac\nu{\alpha\varepsilon^2\mu^2}\leq\frac14.
$$
:::

## Median amplification

::: {.card-cyan}
Independent blocks; $\beta=2\lceil12\ln(1/\delta)\rceil+1$.
$$
Z=\operatorname{median}(A_1,\ldots,A_\beta),\qquad
G=\sum_i\mathbf1[|A_i-\mu|\leq\varepsilon\mu].
$$
$$
\mathbb E G\geq3\beta/4,\qquad
\Pr[|Z-\mu|>\varepsilon\mu]
\leq\Pr[G<\beta/2]\leq e^{-\beta/24}\leq\delta.
$$
:::

::: {.card-green}
$$
M=\alpha\beta=O\left(\left(1+\frac\nu{\varepsilon^2\mu^2}\right)
\log\frac2\delta\right),\qquad\text{aggregation time }O(M).
$$
:::

## Reservoir and suffix rank

::: {.card-purple}
At position $t$: with probability $1/t$, set $(v,r)\gets(s_t,1)$;
otherwise increment $r$ if $s_t=v$.
$$
\Pr[P=p]=\frac1p\prod_{t=p+1}^m\left(1-\frac1t\right)=\frac1m.
$$
$$
r=|\{t\geq P:s_t=s_P\}|,\qquad X=m\bigl(r^k-(r-1)^k\bigr).
$$
:::

::: {.card-orange}
Replacement always resets $r$, including replacement by the same value.
:::

## Unbiasedness by telescoping

::: {.card-green}
$$
\Delta_k(r)=r^k-(r-1)^k.
$$
$$
\mathbb E X
=\frac1m\sum_{i=1}^n\sum_{r=1}^{f_i}m\Delta_k(r)
=\sum_i f_i^k=F_k.
$$
:::

::: {.card-cyan}
$$
k=1:\ X=m;\qquad k=2:\ X=m(2r-1).
$$
More generally, $g(0)=0$ implies
$$
\mathbb E\bigl[m(g(r)-g(r-1))\bigr]=\sum_i g(f_i).
$$
:::

## Squared-increment bound

::: {.card-purple}
For $1\leq r\leq f$,
$$
0\leq\Delta_k(r)\leq kr^{k-1}\leq kf^{k-1}.
$$
$$
\sum_{r=1}^f\Delta_k(r)^2
\leq kf^{k-1}\sum_{r=1}^f\Delta_k(r)=kf^{2k-1}.
$$
:::

::: {.card-green}
$$
\mathbb E X^2=m\sum_i\sum_{r=1}^{f_i}\Delta_k(r)^2
\leq kmF_{2k-1}.
$$
:::

## Compare frequency moments

::: {.card-cyan}
Convexity:
$$
\left(\frac1n\sum_i f_i\right)^k\leq\frac1n\sum_i f_i^k
\quad\Longrightarrow\quad m\leq n^{1-1/k}F_k^{1/k}.
$$
:::

::: {.card-purple}
With $L=\max_i f_i$, $L^k\leq F_k$:
$$
F_{2k-1}\leq L^{k-1}F_k\leq F_k^{(2k-1)/k}.
$$
$$
\boxed{mF_{2k-1}\leq n^{1-1/k}F_k^2.}
$$
:::

## General-moment theorem

::: {.card-green}
$$
\operatorname{Var}(X)\leq\mathbb E X^2\leq kmF_{2k-1}
\leq kn^{1-1/k}F_k^2.
$$
Choose $\alpha=\lceil4kn^{1-1/k}/\varepsilon^2\rceil$ and
$\beta=2\lceil12\ln(1/\delta)\rceil+1$ independent blocks/copies.
:::

::: {.card-purple}
$$
\Pr[|\widehat F_k-F_k|>\varepsilon F_k]\leq\delta,
$$
$$
\text{space and direct time/item: }
O\left(kn^{1-1/k}\varepsilon^{-2}\log\frac2\delta\right).
$$
Fixed $k$; $O(1)$ words per reservoir sketch.
:::

## A signed sketch for $F_2$

::: {.card-cyan}
Unbiased four-wise independent signs $b(i)\in\{-1,+1\}$:
$$
T\gets T+b(s_t),\qquad
T=\sum_{t=1}^m b(s_t)=\sum_{i=1}^n f_ib(i),\qquad X=T^2.
$$
:::

::: {.card-green}
$$
\mathbb E X
=\sum_i f_i^2+2\sum_{i<j}f_if_j\mathbb E[b(i)b(j)]
=F_2.
$$
:::

## Fourth-moment calculation

::: {.card-purple}
| Quadruple pattern | Expected sign product |
|:---|---:|
| $i,i,i,i$ | $1$ |
| At least one singleton index | $0$ |
| Two distinct pairs | $1$ |
:::

::: {.card-green}
$$
\mathbb E T^4=F_4+6\sum_{i<j}f_i^2f_j^2.
$$
$$
\operatorname{Var}(T^2)=4\sum_{i<j}f_i^2f_j^2\leq2F_2^2.
$$
:::

## Polynomial seed

::: {.card-cyan}
Odd prime $n<p=O(\max\{n,2\})$; independent uniform $c_0,\ldots,c_5\in\mathbb F_p$.
$$
g(x)=\sum_{j=0}^5c_jx^j\pmod p.
$$
For $r\leq6$ distinct inputs, the Vandermonde system has rank $r$:
$$
\Pr[g(i_1)=y_1,\ldots,g(i_r)=y_r]=p^{-r}.
$$
:::

::: {.card-purple}
Six coefficients: $O(\log(n+1))$ bits. Fixed-degree evaluation: $O(1)$ word operations.
:::

## Retain zeros and normalize

::: {.card-purple}
$$
b(i)=\begin{cases}
0,&g(i)=p-1,\\
+1,&g(i)\text{ odd},\\
-1,&g(i)\text{ even, }g(i)\neq p-1.
\end{cases}
\qquad q=\frac{p-1}{p}\geq\frac23.
$$
$$
\mathbb E b(i)=0,\qquad\mathbb E b(i)^2=\mathbb E b(i)^4=q.
$$
:::

::: {.card-green}
$$
T=\sum_i f_ib(i),\qquad X=T^2/q,\qquad\mathbb E X=F_2.
$$
No conditioning on nonzero outputs.
:::

## Ternary variance

::: {.card-cyan}
$$
\mathbb E T^4=qF_4+6q^2\sum_{i<j}f_i^2f_j^2.
$$
$$
\begin{aligned}
\operatorname{Var}(T^2/q)
&=(1/q-1)F_4+4\sum_{i<j}f_i^2f_j^2\\
&=2F_2^2+(1/q-3)F_4\leq2F_2^2.
\end{aligned}
$$
:::

## Average the $F_2$ sketches

::: {.card-purple}
$$
\alpha=\lceil16/\varepsilon^2\rceil,\qquad
A_i=\frac1\alpha\sum_{j=1}^\alpha X_{i,j}.
$$
All coefficient vectors are independent.
$$
\operatorname{Var}(A_i)\leq\frac{2F_2^2}{\alpha},\qquad
\Pr[|A_i-F_2|>\varepsilon F_2]\leq\frac18.
$$
:::

## Amplify the $F_2$ estimate

::: {.card-cyan}
$$
U=\sum_i\mathbf1[|A_i-F_2|>\varepsilon F_2].
$$
$$
\Pr[U\geq\beta/2]
\leq7^{-\beta/2}\mathbb E[7^U]
\leq\left(\frac{\sqrt7}{4}\right)^\beta\leq e^{-\beta/4}.
$$
:::

::: {.card-green}
$$
\beta=2\lceil2\ln(1/\delta)\rceil+1,\qquad
\widehat F_2=\operatorname{median}(A_1,\ldots,A_\beta).
$$
$$
\Pr[|\widehat F_2-F_2|>\varepsilon F_2]\leq\delta.
$$
:::

## $F_2$ theorem and resource bounds

::: {.card-green}
For any fixed insertion-only stream and $0<\varepsilon,\delta<1$,
$$
\Pr[(1-\varepsilon)F_2\leq\widehat F_2\leq(1+\varepsilon)F_2]\geq1-\delta.
$$
$$
\boxed{\text{space and time/item: }
O\left(\varepsilon^{-2}\log\frac2\delta\right).}
$$
:::

::: {.card-purple}
Per sketch: six field coefficients and $T\in[-m,m]$; constant-word arithmetic.
Prime selection is preprocessing. Empty stream: return $0$.
:::

## Bounds at a glance

::: {.card-cyan}
| Target | Basic estimator | Relative variance bound |
|:---|:---|:---|
| $F_k$ | $m(r^k-(r-1)^k)$ | $kn^{1-1/k}$ |
| $F_2$ | $(\sum_i f_ib(i))^2/q$ | $2$ |
:::

::: {.card-green}
$$
\text{copies}=O\left((1+R\varepsilon^{-2})\log(2/\delta)\right),
\qquad R\geq\operatorname{Var}(X)/(\mathbb E X)^2.
$$
:::

## Sources {.small}

Notes 28, *Frequency Estimation over a Stream*; results attributed to
[@ams-scafm-99]. Background: [@mr-ra-95].

::: {#refs}
:::