Your job is to pick one ball from a collection of balls in such a way that every ball has an equal probability of being selected. The twist is that you do not know how many balls are in the collection. Each ball will be handed to you, one at a time. As each ball is handed to you you must decide (by some random process) whether to keep or discard the ball.

You must always be holding one and only one ball so that when a new ball is given to you, you must either discard it or keep it by discarding the previously held ball.

(In reply to re: Very Simple by RandyOrton)

The first ball handed to you you keep (until at least the second is handed to you), with probability 1/1, certainty.

The second ball is handed to you, which you keep with 1/2 probability (the other 1/2 you keep the one you were already holding).

So far this is the only thing you could do to have equal probability of either.

If a third ball is handed to you, keep it with 1/3 probability (the other 2/3 you keep the one you were already holding). This assures 1/3 prob. that you then have the third ball, and the 2/3 that are allocated to the ball you are holding is split 1/2, which is 1/2 * 2/3 = 1/3 all together for each of the possibilities of 1st ball and 2nd ball.  So again, if you stop here, you still have equal chances of any of the three balls.

The same with a fourth ball.  If one is presented, give it 1/4 of displacing the one you had before.  That leaves 3/4 chance of keeping the one you had before, but since that is split equally likely among the first three balls, each of those has 1/4 chance also.

And so forth.

Posted by Charlie on 2004-10-22 17:38:27