---
title: Data-Stream Algorithms
module: Data Structures
moduleNumber: 4
lessonNumber: 11
order: 411
summary: |
  Most of this course assumes data sits in fast memory, addressable at will.
  External sorting relaxed that to a re-readable disk. The streaming model goes
  further: items arrive one at a time, are seen once, and must be discarded, with
  only sublinear, often polylogarithmic, memory. In exchange, the answers are
  approximate and probabilistic. We set up the model, then meet reservoir
  sampling for a uniform sample of an unknown-length stream and Morris counting
  for an approximate tally in doubly-logarithmic space.
topics: [Streaming Algorithms, Hashing]
sources:
  - book: CLRS
    ref: "App. C — Probability; Ch. 11 — Hashing"
  - book: Skiena
    ref: "§3.7 — Hashing; §5.x — Randomized Sampling"
  - book: Erickson
    ref: "Ch. — Randomized Algorithms"
practice:
  - title: 'Linked List Random Node'
    slug: linked-list-random-node
    difficulty: Medium
  - title: 'Random Pick with Weight'
    slug: random-pick-with-weight
    difficulty: Medium
  - title: 'Find Median from Data Stream'
    slug: find-median-from-data-stream
    difficulty: Hard
  - title: 'Kth Largest Element in a Stream'
    slug: kth-largest-element-in-a-stream
    difficulty: Easy
---

Almost every algorithm in this course so far has assumed the same machine: the
input sits in memory, and any element is as cheap to touch as any other. That is
the **RAM model**, and it underwrites our analyses of
[hash tables](/algorithms/data-structures/hash-tables),
[balanced trees](/algorithms/data-structures/balanced-trees), and the rest.
[External sorting](/algorithms/sorting/external-sorting) was our first crack in
that assumption: the data was too big for RAM, so we counted block transfers to a
disk we could **re-read** at will. This lesson drops even that assumption. In the
**streaming model**, the input flows past once, item by item, faster and larger
than we can store. We may keep only a tiny working set, and once an item slides
by we may never see it again. The question is what we can still compute.

## Three models, three currencies

It helps to put the models side by side. Each makes a different assumption about
where the data lives and how often we may touch it, and each counts a different
cost.

$$
% caption: Three cost models. The RAM model keeps all $n$ items in memory with full random
%          access. The external-memory model spills to a re-readable disk and counts block
%          transfers. The streaming model sees each item once and keeps only $\mathrm{polylog}(n)$
%          state, trading exact answers for approximate ones.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  box/.style={draw, minimum width=33mm, minimum height=30mm, align=center, inner sep=3pt},
  hd/.style={font=\footnotesize\bfseries}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, fill=acc!8] (ram) at (0,0) {};
  \node[box, fill=acc!8] (ext) at (4.2,0) {};
  \node[box, fill=acc!8] (str) at (8.4,0) {};
  \node[hd] at (ram.north) [yshift=4mm] {RAM mo\/del};
  \node[hd] at (ext.north) [yshift=4mm] {external memory};
  \node[hd] at (str.north) [yshift=4mm] {streaming};
  \node[align=center] at (ram) {all $n$ items\\in memory\\[2mm] random access\\[2mm] exact answers};
  \node[align=center] at (ext) {data on disk\\re-readable\\[2mm] count blo\/ck\\transfers\\[2mm] exact answers};
  \node[align=center] at (str) {one pass\\seen once\\[2mm] polylog space\\[2mm] approximate};
\end{tikzpicture}
$$

> **Definition (Streaming model).** The input is a sequence
> $x_1, x_2, \dots, x_n$ revealed one element at a time. An algorithm reads the
> elements in order, processes each in turn, and maintains a working memory of
> size $s$, the **space** of the algorithm. The goal is $s$ **sublinear** in $n$,
> ideally $\mathrm{polylog}(n)$, far too little to store the stream itself. The
> length $n$ may be unknown in advance and is potentially unbounded.

With so little memory we cannot, in general, answer exactly. The obstruction is
information-theoretic. An algorithm with $s$ bits of memory has at most $2^s$
distinguishable states, so if two different prefixes of the stream drive it into
the same state, its future behavior on any common suffix is identical. For a
question like "were all items distinct?" there are more prefixes demanding
different future behavior than a sublinear memory has states: two different
$\tfrac n2$-element prefixes must be distinguished, because an adversary can
extend each with an element that appears in one but not the other. Counting those
prefixes forces $s = \Omega(n)$ bits for an exact answer, and a similar argument
yields the same bound for the exact median.

So streaming algorithms return **approximate** or **probabilistic** answers,
accepting a small, tunable error in exchange for space that is exponentially
smaller than the stream. This is the same trade a
[Bloom filter](/algorithms/data-structures/skip-lists-and-probabilistic-structures)
makes for set membership, and, as there, the tools are **hashing** and
**randomized analysis**.[^skiena-sample]

> **The streaming trade-off.** Exactness costs space. Given only
> $\mathrm{polylog}(n)$ memory and a single pass, an exact answer is usually
> impossible, but a $(1 \pm \varepsilon)$ approximation, correct with probability
> $1 - \delta$, is often achievable. Tightening $\varepsilon$ or $\delta$ buys
> accuracy back at the cost of more space.

The rest of the lesson is five techniques, each a small variation on that
trade-off: sample the stream, count it, fingerprint its frequencies, find its
heavy hitters, and estimate how many distinct things it contained.

## Reservoir sampling: a uniform sample of unknown length

**Problem.** A stream of $n$ items flows past, with $n$ unknown until the end.
Keep a uniform random sample of $k$ of them, using only $O(k)$ space, so that at
every moment the $k$ stored items are a uniform random $k$-subset of everything
seen so far.

The naive approach, store everything and sample at the end, needs $O(n)$ space
and a known $n$. **Reservoir sampling** removes both costs with one idea: keep a
reservoir of the first $k$ items, then for each later item decide on the spot
whether it displaces one of them.

**Idea.** When the $i$-th item arrives ($i > k$), admit it into the reservoir
with probability $k/i$; if admitted, it evicts a uniformly random current
occupant. In a uniform size-$k$ sample of $i$ items, each item appears with
probability exactly $k/i$, and that is the probability we give it.

```algorithm
caption: $\textsc{Reservoir}(\text{stream}, k)$ — uniform $k$-sample in $O(k)$ space
number: 1
$R[1 \dots k] \gets$ first $k$ items of the stream // fill the reservoir
$i \gets k$
for each remaining item $x$ do
  $i \gets i + 1$ // $x$ is the $i$-th item overall
  $j \gets$ uniform random integer in $[1, i]$
  if $j \le k$ then // happens with probability $k / i$
    $R[j] \gets x$ // evict occupant $j$, admit $x$
return $R$
```

One subtlety in the pseudocode: a single random draw $j \in [1, i]$ decides
both questions at once. The event $j \le k$ has probability exactly $k/i$, which
settles admission, and conditioned on admission $j$ is uniform over $[1, k]$,
which settles who gets evicted. One random number per item, $O(1)$ work per item,
$O(k)$ space total.

$$
% caption: The $i$-th arrival is admitted with probability $k/i$. When admitted it evicts one
%          of the $k$ current occupants, chosen uniformly. The green slot is the new item; the
%          faded slot is the one it replaced.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  slot/.style={draw, minimum width=8mm, minimum height=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % reservoir before
  \node[font=\footnotesize\bfseries] at (1.6,1.5) {reserv{}oir};
  \node[slot, fill=acc!12] (a1) at (0.4,0.6) {$s_1$};
  \node[slot, fill=acc!12] (a2) at (1.2,0.6) {$s_2$};
  \node[slot, fill=acc!12, draw=acc, thick] (a3) at (2.0,0.6) {$s_3$};
  \node[slot, fill=acc!12] (a4) at (2.8,0.6) {$s_4$};
  % new item
  \node[slot, fill=green!18, draw=green, thick] (x) at (5.6,0.6) {$x_i$};
  \node[green, font=\footnotesize] at (5.6,1.7) {item $i$};
  % admit arrow (routed above the reservoir row so it never crosses a slot)
  \draw[acc, ->, thick] (x.north) to[bend right=22] (a3.north);
  \node[acc, font=\scriptsize] at (3.5,2.0) {admit: prob $k$ over $i$};
  % reservoir after: slot 3 now green, old faded
  \node[font=\footnotesize\bfseries] at (1.6,-1.6) {after};
  \node[slot, fill=acc!12] at (0.4,-0.9) {$s_1$};
  \node[slot, fill=acc!12] at (1.2,-0.9) {$s_2$};
  \node[slot, fill=green!18, draw=green, thick] at (2.0,-0.9) {$x_i$};
  \node[slot, fill=acc!12] at (2.8,-0.9) {$s_4$};
  \node[slot, fill=acc!4, draw=acc!30] at (4.4,-0.9) {$s_3$};
  \node[acc!60, font=\scriptsize] at (4.4,-1.7) {evicted};
  \draw[acc!50, ->] (2.0,0.18) -- (2.0,-0.5);
\end{tikzpicture}
$$

**A worked trace.** Run the algorithm with $k = 2$ on the stream
$a, b, c, d, e$. The first two items fill the reservoir, so after $i = 2$ it
holds $\{a, b\}$. Then the coin flips begin.

- **Item $c$ ($i = 3$).** Draw $j \in [1, 3]$; admission needs $j \le 2$, which
  happens with probability $2/3$. Suppose $j = 1$: $c$ is admitted and evicts
  the occupant of slot $1$. Reservoir: $\{c, b\}$.
- **Item $d$ ($i = 4$).** Admission probability $2/4 = 1/2$. Suppose $j = 4$:
  the draw exceeds $k$, so $d$ is rejected and discarded forever. Reservoir
  unchanged: $\{c, b\}$.
- **Item $e$ ($i = 5$).** Admission probability $2/5$. Suppose $j = 2$: $e$ is
  admitted and evicts slot $2$. Reservoir: $\{c, e\}$.

$$
% caption: Reservoir sampling with $k = 2$ on the stream $a, b, c, d, e$. Items $a, b$ fill the
%          reservoir; each later arrival $i$ is admitted with probability $k/i$ ($2/3$, then
%          $1/2$, then $2/5$) and, when admitted, evicts a uniformly chosen occupant. This run
%          admits $c$ and $e$, rejects $d$, and ends at $\{c, e\}$.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  slot/.style={draw, minimum width=8mm, minimum height=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % headers
  \node[font=\footnotesize\bfseries] at (0,0.9) {arriv{}al};
  \node[font=\footnotesize\bfseries] at (2.7,0.9) {reserv{}oir after};
  \node[font=\footnotesize\bfseries, anchor=west] at (4.6,0.9) {decision};
  % row: fill phase
  \node[acc, font=\scriptsize] at (-1.7,0) {$i$ = 1, 2};
  \node[slot, fill=acc!12] at (-0.45,0) {$a$};
  \node[slot, fill=acc!12] at (0.45,0) {$b$};
  \node[slot, fill=acc!12] at (2.3,0) {$a$};
  \node[slot, fill=acc!12] at (3.1,0) {$b$};
  \node[anchor=west, black] at (4.6,0) {f\/irst $k$ = 2 items f\/ill the slots};
  % row: c arrives
  \node[acc, font=\scriptsize] at (-1.7,-1.4) {$i$ = 3};
  \node[slot, fill=green!18, draw=green, thick] at (0,-1.4) {$c$};
  \node[slot, fill=green!18, draw=green, thick] at (2.3,-1.4) {$c$};
  \node[slot, fill=acc!12] at (3.1,-1.4) {$b$};
  \node[anchor=west, green] at (4.6,-1.4) {admit (prob 2/3): evict slot 1};
  % row: d arrives
  \node[acc, font=\scriptsize] at (-1.7,-2.8) {$i$ = 4};
  \node[slot, fill=acc!4, draw=black] at (0,-2.8) {$d$};
  \node[slot, fill=acc!12] at (2.3,-2.8) {$c$};
  \node[slot, fill=acc!12] at (3.1,-2.8) {$b$};
  \node[anchor=west, black] at (4.6,-2.8) {reject (prob 1/2): unchanged};
  % row: e arrives
  \node[acc, font=\scriptsize] at (-1.7,-4.2) {$i$ = 5};
  \node[slot, fill=green!18, draw=green, thick] at (0,-4.2) {$e$};
  \node[slot, fill=acc!12] at (2.3,-4.2) {$c$};
  \node[slot, fill=green!18, draw=green, thick] at (3.1,-4.2) {$e$};
  \node[anchor=west, green] at (4.6,-4.2) {admit (prob 2/5): evict slot 2};
\end{tikzpicture}
$$

The run above is one sample path; the theorem below says that averaging over all
coin flips, every one of the $\binom{5}{2} = 10$ pairs is equally likely, and
each individual item ends up retained with probability exactly $2/5$. This
local rule produces a globally uniform sample at
every prefix, not just at the end: stop the stream after any $i$, and the
reservoir is a uniform $k$-subset of the first $i$ items.

> **Theorem (Uniformity).** After the stream has delivered $n \ge k$ items, every
> one of the items is in the reservoir with probability $k/n$, and every
> $k$-subset is equally likely.

> **Proof.** Fix an item that arrived at position $i$. If $i \le k$ it entered the
> initial reservoir with probability $1$; if $i > k$ it was admitted with
> probability $k/i$. To remain at the end it must _survive_ every later arrival.
> When item $t > i$ arrives ($t > k$), it is admitted with probability $k/t$ and
> then evicts a uniformly chosen occupant, so our item is evicted with probability
> $\tfrac{k}{t}\cdot\tfrac{1}{k} = \tfrac1t$, hence survives step $t$ with
> probability $1 - \tfrac1t = \tfrac{t-1}{t}$. Multiplying the admission
> probability by all survival probabilities telescopes:
> $$
> \Pr[\text{item } i \text{ in } R] \;=\; \frac{k}{i}\cdot\prod_{t=i+1}^{n}\frac{t-1}{t}
> \;=\; \frac{k}{i}\cdot\frac{i}{i+1}\cdot\frac{i+1}{i+2}\cdots\frac{n-1}{n}
> \;=\; \frac{k}{i}\cdot\frac{i}{n} \;=\; \frac{k}{n}.
> $$
> For $i \le k$ the item is admitted with probability $1$ and must survive every
> arrival from $t = k+1$ onward:
> $1 \cdot \prod_{t=k+1}^{n} \tfrac{t-1}{t} = \tfrac{k}{n}$ again. Since the bound
> is identical for every item and the construction is symmetric, all $k$-subsets
> are equally likely. $\qed$

Check the theorem against the trace: item $c$ arrived at $i = 3$, so it should
be retained with probability
$\tfrac23 \cdot \tfrac34 \cdot \tfrac45 = \tfrac25$, admission times two
survivals. Item $a$, present from the start, must survive the arrivals at
$i = 3, 4, 5$, each of which evicts it with probability $\tfrac1i$:
$\left(1 - \tfrac13\right)\left(1 - \tfrac14\right)\left(1 - \tfrac15\right) =
\tfrac23 \cdot \tfrac34 \cdot \tfrac45 = \tfrac25$ as well. Every path through
the coin flips is different; the retention probability is not.

**Edge cases and variants.** If the stream ends with $n < k$ items, the
reservoir simply holds all of them, which is the only correct answer. The
special case $k = 1$ is worth memorizing on its own: keep one item, and replace
it with the $i$-th arrival with probability $1/i$. That is the entire solution
to _Linked List Random Node_, a uniform pick from a list of unknown length in
one pass and $O(1)$ space. For very long streams where the random-number
generator is the bottleneck, the admission probability $k/i$ shrinks, so most
draws are rejections; one can instead draw, in $O(1)$ time, the _number of items
to skip_ before the next admission, and fast-forward. And when items carry
weights $w_i$ and the sample should favor heavy items, a weighted variant
assigns each item the key $u_i^{1/w_i}$ for a uniform $u_i \in (0,1)$ and keeps
the $k$ largest keys in a small heap; unweighted reservoir sampling is the
special case where all weights are $1$. (The LeetCode problem _Random Pick with
Weight_ is the offline cousin: with all weights in memory, prefix sums and a
binary search do the job.)

Reservoir sampling underlies A/B test logging, random log extraction, and fair
sampling anywhere the choice is from a sequence whose length is learned only at
the end.

::impl{algo="reservoir_sampling"}

## Morris counting: a count in $O(\log\log N)$ bits

**Problem.** Count events up to $N$, but spend far fewer than the $\log_2 N$ bits
an exact counter needs.

**Idea.** Don't store the count $c$; store an exponent $X$ that approximates
$\log_2 c$. On each increment, advance $X$ only _probabilistically_, with
probability $2^{-X}$, so that $X$ grows by one roughly every time the true count
doubles. The estimate read out is $\hat c = 2^{X} - 1$.

```algorithm
caption: $\textsc{Morris}$ — approximate counting in $O(\log\log N)$ bits
number: 2
$X \gets 0$
procedure $\textsc{Increment}()$
  with probability $2^{-X}$ do // one biased coin flip
    $X \gets X + 1$
procedure $\textsc{Query}()$
  return $2^{X} - 1$ // unbiased estimate of the count
```

Because $X$ only needs to reach about $\log_2 N$, storing $X$ takes
$O(\log\log N)$ bits, an exponential saving over the counter it approximates.
Counting to a billion takes $X \le 30$, which fits in $5$ bits.

**A worked trace.** One possible run of ten increments:

| increment | $\Pr[\text{bump}]$ | coin  | $X$ after | $\hat c = 2^X - 1$ |
| --------- | ------------------ | ----- | --------- | ------------------ |
| 1         | $1$                | up    | $1$       | $1$                |
| 2         | $1/2$              | up    | $2$       | $3$                |
| 3         | $1/4$              | stay  | $2$       | $3$                |
| 4         | $1/4$              | stay  | $2$       | $3$                |
| 5         | $1/4$              | up    | $3$       | $7$                |
| 6–10      | $1/8$              | stay  | $3$       | $7$                |

After ten increments the estimate reads $7$ against a true count of $10$: off by
$30\%$, which is typical, since a single Morris counter has constant relative
error. The estimate is coarse but never drifts systematically, and that is the
precise content of the next claim.

> **Theorem (Unbiasedness).** After $c$ increments,
> $\mathbb{E}\!\left[2^{X} - 1\right] = c$.

> **Proof.** Write $Y_c = 2^{X_c}$ for the estimator's raw value after $c$
> increments. Condition on the current state $X_c = x$. The next increment raises
> $X$ with probability $2^{-x}$ and leaves it alone otherwise, so
> $$
> \mathbb{E}\!\left[Y_{c+1} \mid X_c = x\right]
> \;=\; 2^{-x}\cdot 2^{\,x+1} + \left(1 - 2^{-x}\right)\cdot 2^{x}
> \;=\; 2 + 2^{x} - 1
> \;=\; 2^{x} + 1.
> $$
> Taking expectations over $X_c$ gives the recurrence
> $\mathbb{E}[Y_{c+1}] = \mathbb{E}[Y_c] + 1$: every increment adds exactly one to
> the expectation, whatever the distribution of the current state. Since $X_0 = 0$
> gives $Y_0 = 1$, induction yields $\mathbb{E}[Y_c] = c + 1$, hence
> $\mathbb{E}[2^{X_c} - 1] = c$. $\qed$

**Variance, and how averaging fixes it.** The same conditioning computes the
second moment. With $Z_c = 4^{X_c}$,
$$
\mathbb{E}\!\left[Z_{c+1} \mid X_c = x\right]
= 2^{-x}\cdot 4^{\,x+1} + \left(1 - 2^{-x}\right)\cdot 4^{x}
= 4^{x} + 3\cdot 2^{x},
$$
so $\mathbb{E}[Z_{c+1}] = \mathbb{E}[Z_c] + 3\,\mathbb{E}[Y_c] =
\mathbb{E}[Z_c] + 3(c+1)$, and summing from $Z_0 = 1$ gives
$\mathbb{E}[4^{X_c}] = 1 + \tfrac{3c(c+1)}{2}$. Therefore
$$
\Var\!\left[2^{X_c}\right]
= \mathbb{E}[4^{X_c}] - \left(\mathbb{E}[2^{X_c}]\right)^2
= 1 + \tfrac{3c(c+1)}{2} - (c+1)^2
= \frac{c(c-1)}{2}.
$$
The standard deviation is about $c/\sqrt{2}$, comparable to the count itself, so
one counter is only good to a constant factor. Chebyshev's inequality makes the
repair quantitative: averaging $m$ independent counters divides the variance by
$m$, so
$$
\Pr\!\left[\,\lvert \bar{\hat c} - c\rvert > \varepsilon c\,\right]
\;\le\; \frac{c(c-1)/(2m)}{\varepsilon^2 c^2}
\;\le\; \frac{1}{2\,\varepsilon^{2} m},
$$
which drops below $\delta$ once $m \ge 1/(2\varepsilon^{2}\delta)$. The total
space is $O(\varepsilon^{-2}\delta^{-1}\log\log N)$ bits, still exponentially
below an exact counter for fixed accuracy.[^clrs-prob] Alternatively,
replacing base $2$ by $1 + 1/b$ makes $X$ advance more often and shrinks the
per-counter variance at the cost of a slightly larger register.

> **Guarantee.** Morris's counter is **unbiased**: $\mathbb{E}[2^{X} - 1] = c$
> after $c$ increments. Its relative error is constant; averaging $m$ independent
> counters cuts the variance by a factor $m$, giving a $(1\pm\varepsilon)$
> estimate with probability $1 - \delta$ in $O(\varepsilon^{-2}\delta^{-1}
> \log\log N)$ bits.

Morris counting anticipates the sketches that follow: a single
small random variable standing in for a quantity too large to store exactly, made
accurate by averaging independent copies.[^erickson-rand]

::impl{algo="morris_counter"}

## Where sampling and counting run

Reservoir sampling and Morris counting are old ideas, 1985 and 1978
respectively, that never went away, because the problems they solve, sampling a
stream whose length you learn only at the end and counting without room for a
counter, keep recurring at scale.

**Reservoir sampling** (Vitter, 1985, who named it and gave the skip-ahead
optimization) is the standard way to draw a fair sample from a log you cannot
buffer: distributed systems use it to keep a bounded, uniform sample of requests
for tracing and A/B analysis, and Apache Kafka and Spark ship variants. The
weighted generalization, keying each item by $u_i^{1/w_i}$ and keeping the top
keys, is the **A-Res** algorithm of Efraimidis and Spirakis (2006), used
when items should be sampled with unequal probability, such as sampling clicks
in proportion to dwell time.

**Morris counting** (Morris, 1978, analyzed rigorously by Flajolet in 1985)
foreshadowed a whole family of probabilistic counters. Its modern descendants
are the _approximate counters_ inside monitoring systems that must track
billions of events per second in a fixed register budget, where the constant
relative error is a fair price for shrinking a $\log N$-bit counter to
$\log\log N$ bits. The averaging trick that repairs its variance, run $m$
independent copies and average, is the same move that turns the noisy sketches
of the [next lesson](/algorithms/data-structures/streaming-sketches) into
trustworthy estimators.[^btb-sampling]

## Continuing on to sketches

Reservoir sampling and Morris counting each summarized the stream _as a whole_,
a representative subset, a single approximate total. The harder and more common
questions are about the stream's _contents_: how often did a particular item
appear, which items are frequent, how many distinct items were there? Answering
those in sublinear space calls for **sketches**, small hashed counter arrays
with the same exactness-for-space trade-off pushed one level further. This
continues in [Streaming Sketches](/algorithms/data-structures/streaming-sketches).


## Takeaways

- The **streaming model** processes $x_1, \dots, x_n$ in one pass, keeping only
  $\mathrm{polylog}(n)$ state; items are seen once and discarded. An
  information-theoretic argument forces exact answers to cost $\Omega(n)$ space,
  so the model trades exactness for **approximate, probabilistic** answers.
- The three cost models line up by what they assume about the data: **RAM**
  (fits, freely re-readable, spends _time_, exact), **external memory**
  (re-readable but too big, spends _block transfers_, exact), **streaming**
  (seen once, spends _space_, approximate).
- **Reservoir sampling** keeps a uniform $k$-sample of an unknown-length stream in
  $O(k)$ space by admitting item $i$ with probability $k/i$; the telescoping
  product $\frac{k}{i}\prod_{t>i}\frac{t-1}{t} = \frac{k}{n}$ makes every item
  equally likely to be retained, at every prefix. The case $k = 1$ is a uniform
  pick from a list of unknown length in $O(1)$ space.
- **Morris counting** approximates a count up to $N$ in $O(\log\log N)$ bits with
  the unbiased estimator $2^{X}-1$; its variance $c(c-1)/2$ is cut by averaging
  independent copies, the same technique the sketches of the next lesson use.
- These two summarize the stream as a whole; estimating its per-item frequencies
  needs the [sketches](/algorithms/data-structures/streaming-sketches) that follow.

[^skiena-sample]: **Skiena**, §3.7 and the randomized-sampling discussion: hashing as the engine of streaming sketches, and uniform sampling without replacement from a sequence.
[^clrs-prob]: **CLRS**, App. C — Counting and Probability: the expectation, Markov-inequality, and union-bound arguments behind the reservoir and Morris-counter guarantees.
[^erickson-rand]: **Erickson**, Ch. — Randomized Algorithms: analysis of estimators by their expectation and variance, and the averaging trick that drives accuracy with independent copies.
[^btb-sampling]: Vitter, "Random sampling with a reservoir" (1985); Efraimidis & Spirakis, "Weighted random sampling with a reservoir" (A-Res, 2006); Morris, "Counting large numbers of events in small registers" (1978), analyzed by Flajolet, "Approximate counting: a detailed analysis" (1985).