Pick one uniformly random item from a stream

Question

Items arrive one at a time from a source whose total count n you never learn (a log tail, a socket, an iterator). You may store only a constant amount of state.

Return one item so that each of the n items has probability exactly $1/n$ of being chosen. Prove it.

Accepted Answer

This is reservoir sampling with k = 1. Hold one "current pick." When the item at index i (0-indexed) arrives, replace the current pick with probability 1/(i+1); otherwise keep what you have. Why it is uniform. Item i becomes the current pick with probability 1/(i+1). To survive to the end it must then avoid being overwritten at every later step t, and the overwrite probability at step t is 1/(t+1). So its final probability is \frac{1}{i+1}\prod{t=i+1}^{n-1}\left(1 - \frac{1}{t+1}\right) = \frac{1}{i+1}\cdot\frac{i+1}{i+2}\cdot\frac{i+2}{i+3}\cdots\frac{n-1}{n} = \frac{1}{n}. The product teles…

Pick one uniformly random item from a stream

Your answer

More Coding questions