Derivation of Reservoir Sampling


I had to implement reservoir sampling during an interview and I had no idea how to do that. So I had to figure it out on the spot. This is where all those years of induction paid off, since there’s a nice derivation based on writing down the definitions of everything and noticing that there’s a natural inductive pattern.

The Problem

Sample elements from a stream.

Definitions

Sample
Uniformly at random.
Stream
A sequence of finite length (uniform sampling wouldn’t make sense on a countably infinite sequence). It can only be accessed one element at a time in a linear order, and is exhausted by iteration.

Python iterators like (i for i in range(5)) are good examples of streams.

The Solution

The constraints of the stream data structure suggest a solution that comes from considering simple cases and noticing that you don’t know how long the stream is.

We need an algorithm that works for any length, but we don’t know what that length is up front. All we get is one element at a time (with something like StopIteration when the stream is empty) and all we can do with that element is store or ignore it.

Let’s call that unknown length and consider simple cases.

For now, assume . We only want to sample a single element.

Our stream has only one element. Let’s call it . We only find out that there’s one element when we try to access it twice and get and then StopIteration.

So for our algorithm to cover this case, it has to store no matter what.

Since we don’t know that , we have to cover the case and keep .

Then to have a uniform sampling over , we have to discard and keep with probability .

This is the case with one additional element. So we keep with probability 1 and with probability .

To keep the sampling uniform, you’ll see that needs to be kept with probability .

This suggests a pattern of keeping the -th element with probability . This is correct, and I’ll let you look up the proof on Wikipedia.

Now we consider how to sample elements rather than just 1. We start with the smallest valid case.

As before, we need to keep the first elements no matter what in case there are no others.

(The data structure that stores these elements is our reservoir).

A bit of arithmetic shows that we need to keep our -th element with probability .

If we keep it, we uniformly pick one element from our reservoir and replace it with this new element.

And then we’re done. The stream data structure’s constraints of unknown length and nonrandom access basically solves the problem for us.

Related Posts

Swastika Night

Is there a name for this construction?

Fun with negation and idioms

How to change tabs to spaces

Another Way to Write Conditional Probability

Notes for May 9, 2019

A tool to look at random images

Safeway

e-ink reminisces

Edwin Edwards