Pick a Uniformly Random Character From a Stream of Unknown Length
A file contains a sequence of characters. You may read the file only once, sequentially, one character at a time, and you do not know its length in advance (and cannot afford to store the whole file). When you reach the end, you must output a single character chosen so that each character in the file is equally likely to be the one selected.
Design an algorithm that uses $O(1)$ memory, and prove that it is uniform.
Hints
- You must commit to a candidate as you go, but be willing to replace it. The question is with what probability to replace the current candidate when the $k$-th character arrives.
- Keep the $k$-th character with probability $1/k$ (replace the current pick), otherwise keep the current pick. Then the last character is selected with probability $1/m$ trivially.
- Induction on $k$: if after $k$ characters each has probability $1/k$, then after character $k+1$ arrives, each earlier one has probability $\frac1k\cdot\frac{k}{k+1} = \frac{1}{k+1}$.
Worked Solution
How to Think About It: You cannot wait until the end because you do not know when the end is and cannot store everything; you cannot decide early because later characters deserve an equal chance. The resolution is to always hold one candidate and let each new character overthrow it with a carefully chosen probability, so that uniformity holds after every prefix. Then the unknown stopping point does not matter.
Approach: Reservoir sampling with a reservoir of size one; prove uniformity by induction on the number of characters read.
Formal Solution:
*Step 1 -- Algorithm.* Maintain a counter $k$ and a single stored character pick. - Read the first character; set pick to it ($k = 1$). - When the $k$-th character $x_k$ arrives ($k \ge 2$): with probability $1/k$ set pick $= x_k$; with probability $1 - 1/k$ leave pick unchanged. - At end of file, output pick.
```python import random def reservoir_pick(stream): pick = None for k, ch in enumerate(stream, start=1): if random.randrange(k) == 0: # probability 1/k pick = ch return pick ```
Memory is $O(1)$ (one character and one counter); time is $O(m)$ for a file of $m$ characters, one random number per character.
*Step 2 -- Uniformity by induction.* Claim: after the first $k$ characters have been processed, $P(\text{pick} = x_i) = 1/k$ for every $i \le k$. - Base case $k = 1$: the pick is $x_1$ with probability $1$. - Inductive step: assume the claim for $k$. When $x_{k+1}$ arrives, it becomes the pick with probability $1/(k+1)$. For $i \le k$, $x_i$ remains the pick if it was the pick before (probability $1/k$ by hypothesis) and $x_{k+1}$ is rejected (probability $k/(k+1)$, independent of the past): $$P(\text{pick} = x_i) = \frac1k\cdot\frac{k}{k+1} = \frac{1}{k+1}.$$ So all $k + 1$ characters have probability $1/(k+1)$.
*Step 3 -- Conclusion.* If the file has $m$ characters, the output is $x_i$ with probability $1/m$ for each $i$, regardless of $m$, and the algorithm never needed to know $m$. Direct computation confirms this: $P(\text{pick} = x_i) = \frac1i\prod_{k=i+1}^{m}\left(1 - \frac1k\right) = \frac1i\cdot\frac{i}{m} = \frac1m$ (telescoping product).
*Step 4 -- Generalization.* To pick $s$ characters uniformly without replacement, store the first $s$; when the $k$-th ($k > s$) arrives, with probability $s/k$ replace a uniformly chosen stored item. The same induction shows every character ends up in the reservoir with probability $s/m$ and every $s$-subset is equally likely. A simulation of the single-pick algorithm on a 10-character stream ($500{,}000$ runs) gave counts between $49{,}500$ and $50{,}400$ per character, consistent with $50{,}000$.
Answer: Reservoir sampling: keep one candidate; when the $k$-th character arrives, replace the candidate with it with probability $1/k$. By induction each of the first $k$ characters is the candidate with probability $1/k$, so at end of file (length $m$) every character is chosen with probability $1/m$, using $O(1)$ memory and $O(m)$ time.
Intuition
Reservoir sampling solves an apparently impossible bookkeeping problem with one number: when the $k$-th item arrives, adopt it with probability $1/k$. Each survivor's probability is then diluted by exactly the factor $k/(k+1)$ at the next step, so at every moment every item seen so far is equally likely to be the current pick, and the process is uniform no matter where the stream stops. This is the standard tool for sampling from tick data or log files that are too large to hold, and its $k$-item generalization (keep the first $k$, replace a random slot with probability $k/n$) powers streaming estimators of quantiles and subsampled backtests.