# Reservoir Sampling vs Round Robin

You are given a List of numbers (length unknown).

Let's say the length is 10.

GetRandom(List) is called once. If implemented correctly, each number has 1/10 probability of being returned.

GetRandom(List) is called 100 times. If implemented correctly, each number will appear 10 times in the result.

Fine?

You now have to do the same for a Stream of numbers.

GetRandom(Stream, 5) is called. This adds 5 to the Stream. Stream is of length N=1, then 5 is returned (probability = 1/N = 1)

GetRandom(Stream, 3) is called. 3 is added to stream. N=2. Either 3 or 5 is returned (prob = 1/2).

How will this be tested for correctness?
If GetRandom(Stream) (without adding any more numbers) is called 10 times when length of list is 2, each number (3 & 5) should be returned ~5 times.

GetRandom(Stream, 7) is called. 7 is added to Stream. N = 3. One of the 3 numbers (5, 3, 7) is returned (probability = 1/3).

But how will this be tested for correctness?
If GetRandom(Stream) is called 10 times when N = 3, each number is returned ~3 times.

So far, so good ?

Alright, here is my algorithm:

N = 0
Pointer = 0

GetRandom(Stream, Number = NULL):
Pointer += 1

if Number is NOT NULL:
N += 1
else:
if Pointer == N:
Pointer = 1    # Reset

return Stream[Pointer]    # Assume 1-based indexes


This simply cycles through all numbers in order / round-robin fashion.

If GetRandom(Stream) is called on a Stream with 100 numbers, 1000 times, each number will appear exactly 10 times.

If GetRandom(Stream, 77) is called on a Stream with 100 numbers (77 is the 101st number), while Pointer got reset to initial location 1. Then when GetRandom(Stream) is called 101 times, then on the 101st call, 77 will be output, which satisfies the required probability of 1/101. If it's called 202 times, then on the 202th call, 77 will be output, which satisfies 2/202.

Why bother with Reservoir Sampling k/k+1, Why bother with a random number generator?

• Average probability of the events is not the only measurement for randomness. Your algorithm yields a sequence with high autocorrelation. Feb 13 '20 at 13:52
• @Albjenow, how do you know that correlation was a result of the algorithm and not because of randomness.. are you saying that 'randomly generated numbers should NOT be sequential' - if you are imposing 'your' rules on 'randomness', that defeats the purpose of random, doesn't it? It's like saying - "if I toss a coin twice, and get HHTT, it's right, but if it get HTHT, it's wrong" Feb 13 '20 at 20:12
• I am surprised there are even CS@SE tags for what I think purely mathematical concepts. Feb 13 '20 at 21:43
• – D.W.
Feb 14 '20 at 0:58
• You were the first to impose rules on randomness by saying "If GetRandom(Stream) is called on a Stream with 100 numbers, 1000 times, each number will appear exactly 10 times." According to that, a sequence of 1000 42s is not random. The most loose definition of randomness is a sequence without (obvious) patterns. ... Feb 14 '20 at 7:45