Puzzles, Maths and Algorithms: Picking an Element Randomly from Stream

Puzzles, Maths and Algorithms: Picking an Element Randomly from Stream

How to pick a number randomly from a stream (or a linked list) with a finite but unknown length N? Solution must use constant space and guarantee that number is picked with probability = 1/N.

Solution:
If we know the length of the stream, then problem is trivial. Simply generate a random number r between 1 and N. Declare the number at index r as the desired random number.

For an unknown but finite N, we need that elements are selected with equal probability. Let us first build the loop invariant property for the solution. Say we have seen k elements so far, the selected number (say n) must be selected with probability 1/k. As we see a new element (say n1), we should set n=n1 with probability 1/(k+1). This ensures that n1 is selected with probability 1/(k+1). In the other case, n (the one NOT replaced by n1) is selected with probability = 1/k * (1-1/(k+1)) = 1/(k+1). Hence this strategy ensures that a number a selected with probability 1/N for N>=k. This loop invariant is adhered by the following code:

n=0, N=0  while Stream.hasElement()    ++N    if rand <= 1/N       n = Stream.nextElement()  return n  

After the algorithm processes all elements, n would contain the randomly selected element and N would contain the number of elements in the stream.

Read full article from Puzzles, Maths and Algorithms: Picking an Element Randomly from Stream