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 No Subject by bob909)

When I see algorithm and random in the same problem, I cringe. 

Here's my solution: I will keep a ball when "The Mood" strikes me. No one, including me, knows when that might be. It might be the first ball, some ball in between, or I might be left holding the last ball.  Every ball has an equal probability of being selected, I do not know how many balls I will be handed.  Repeat the process however many times you like, and each and every time I will select one and only one ball from the collection, completely at random.

If we do this 10 times, and every time I select the first ball, what are the chances I will select the first ball on the next go around? Some may say I'm biased and will pick the first ball again.  Wouldn't a truely random process allow for picking the first ball 10 times in a row?

I think it is a catch 22 to prove that an algorithm is truly random. There must be some famous work somewhere that shows that random-ness is unprovable.

Posted by bob909 on 2004-10-23 07:37:12