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.