Reservoir sampling from a stream

Question

A stream emits items one at a time and you do not know its length n in advance (it may not fit in memory). Draw k items so that every item has an equal k/n chance of ending up in your sample.

Implement it in a single pass using $O(k)$ memory, then prove each item is kept with probability exactly $k/n$ .

reservoir_sample(range(1000), k=5)  ->  5 items, each equally likely

Accepted Answer

Fill the reservoir with the first k items. For each later item at index i, pick a random integer j in [0, i]; if j < k, overwrite slot j with the new item (otherwise discard it). This is Algorithm R. Why it's uniform. The i-th item (0-indexed) is admitted with probability k / (i+1), since j < k happens for k of the i+1 equally likely values. For it to survive to the end, it must then dodge replacement at every later step t i: replacement of any specific slot at step t has probability 1/(t+1), so survival is \frac{k}{i+1} \prod{t=i+1}^{n-1}\left(1 - \frac{1}{t+1}\right) = \frac{k}{i+1}\cdot\fr…

Reservoir sampling from a stream

Your answer

More Coding questions