Select an element from a stream with uniform distributed probability

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.

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.