In @nodakaiâ€™s experiment, the length of the iterator is 3 and the size of the reservoir is 1. The `sample`

function starts by filling the reservoir with the first element in the iterator, so the probability of each element being in the reservoir is:

**before i=0:** [100%, 0%, 0%]

The first element is definitely in the reservoir.

Then the `sample`

function begins replacing elements in the reservoir, starting with i=0. For i=0 it generates a uniformly distributed random integer in the range `[0, i+1+amount)`

which is `[0, 2)`

, so either 0 or 1 with equal probability. If the random integer is 0, it replaces the element in the reservoir with the second element in the iterator:

**after i=0:** [50%, 50%, 0%]

The first element in the iterator has a 50% probability of having been removed from the reservoir, and the second element in the iterator has a 50% probability of having been added to the reservoir.

Moving on to i=1, the `sample`

function generates a uniformly distributed random integer in the range `[0, i+1+amount)`

which is `[0, 3)`

, so 0 or 1 or 2 with equal probability. If the random integer is 0, it replaces the element in the reservoir with the third element in the iterator:

**after i=1:** [33.3%, 33.3%, 33.3%]

The element currently in the reservoir before i=1 has a 1/3 probability of being removed when i=1, so it has a 2/3 probability of *not* being removed. The probability for each of the first 2 elements in the iterator to be in the reservoir after i=1 is the probability that they were in the reservoir before i=1, multiplied by the probability that they were not removed from the reservoir at i=1, so 50% * 2/3 which is 33.3%.

The result is that all 3 elements in the iterator have a 1/3 chance of being in the final reservoir of size 1. In general for an iterator of length N and a reservoir of size M, each element has a M/N probability of being in the reservoir.

As a second example, for N=6 and M=3 the probabilities work like this:

**before i=0:** [100%, 100%, 100%, 0%, 0%, 0%]

**after i=0:** [75%, 75%, 75%, 75%, 0%, 0%]

**after i=1:** [60%, 60%, 60%, 60%, 60%, 0%]

**after i=2:** [50%, 50%, 50%, 50%, 50%, 50%]