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(2): No Subject by Federico Kereki)

My method is random AND guarantee's that each and every ball has a 1/n probability of being selected, since only one ball WILL be selected from the entire sample.  In my book 1/n = 1/n.  I think if you have some predetermined probability associacted with each ball, ie flip a coin or pick a card, you end up favoring early balls or later balls, and this balls everything up.

If your random method has a greater than 1/n probability for each ball then the overall process will be skewed towards picking a ball at the beginning or at the end, depending on whether or not you are using the probability to keep or discard a ball.  If the probability for each ball is much less than 1/n you end up picking the last ball.

I think to be fair, your algorithm needs to pick each ball with a 1/n chance, but like the problem states, you don't know what n is ahead of time to write the algorithm using 1/n.

Posted by bob909 on 2004-10-26 07:56:41