Select an element from a stream with uniform distributed probability

Question

Give you:

1. A stream (end of the stream is EOF)
2. A function next() to get the next element in the stream and advance the pointer in the stream
3. A random generator generating floats between 0 and 1 (inclusively) uniformly

Output:

• An element that is proven to be randomly (uniformly distributed) chosen

You can one or two variables.

You are not allowed to use array / list, and you cannot tell the way that trying to get all elements out and store them all and then pick.

---

This is an interview question.

My thinking is:

1. I use a var cur to store most recent kept element
2. So, if i get a new element, I generate a random 0 or 1 using generator, if it is 0 then cur = new element; otherwise, continue;
3. If I get EOF, then return cur

---

Is my thinking correct? How to prove?

---

Here is a same question

How would you pick a uniform random element in linked list with unknown length?

Answer 1

Let the current element's index be i.

Choose to 'remember' the current element at probability 1/i. When EOF is reached, produced the element you remember.

At the end, for each element with index i there is a probability to be chosen:

A formal prove can be done using induction, following these guidelines.

Answer 2

This algorithm chooses the last element in the stream with a probability of 1/2, so unless the stream has size = 2, this is not a valid solution.

A valid way would be to assign a random float value drawn from a uniform distribution between [0..1] to every element and return the one with the largest (or smallest) value at the end. This can be done in O(1) auxiliary space, you just need to remember the largest value and the associated element.

Answer 3

This solution doesn't quite fit all of the parameters in the question. However, this solution is based on a real-world need and code.

private static final SecureRandom s_random = new SecureRandom();  // Use SecureRandom for truly random selection without a pattern

public static <V> V randomValue(Iterator<V> values)
{
   V result, item;
   int count;

   result = null;

   for (count = 1, values.hasNext(); count++)
   {
      item = values.next();

      if (count == 1)  // Always select the first element
         result = item;
      else if (s_random.nextnextInt(count) == 0)  // Replace the previous random item with a new item with 1/count probability
         result = item;
   }

   if (result == null)
      throw new IllegalArgumentException("No value found");

   return(result);
}

The above algorithm is taken from here

Answer 4

Here's my python code for this problem (also available with tests on my github):

import random as rnd

def sample(iterator):
    """ Uniform sampling of an element from an stream.
    The i-th element (indexed at 1) is sampled with probability 1/i.
    This can be shown by recurrence to lead to uniform sampling. 
    Indeed, at step n we impose p(val==n)=1/n, and all elements i before n 
    were sampled with equal probability, which is also equal to 1/n since
    p(val<n) = (n-1)*p(val==i) = 1-1/n = (n-1)/n => p(val==i) = 1/n """
    i = 1
    out = None
    for elm in iterator:
        if rnd.uniform(0,1) <= 1/i:
            out = elm
        i += 1
    return out