Wednesday, March 28, 2007

Probability puzzle: Uniform Everytime

Assume I have a bag with several distinct objects. Particularly, I do not tell you how many objects I have. At each step, I take out one item and give it to you. I may do this in any order, with any probability distribution or even adversarially. You can only hold one item in your hand at a time. So, at each step, you get to choose whether to retain the object already in hand or replace it with the new one. When I run out of objects (or I am simply tired and quit), I stop.

Your goal is adopt a strategy so that the object in your hand at the end is uniformly at random among all items. In other words, irrespective of how many objects I give you or however I choose them, this item in your hand should be equally probable to any other item.

Go figure!
(courtsey Nenad)

1 comment:

dBera said...

Here is how you do it: at the 1-st step, say you get item i. You want to retain the item i with probability 1 if I stop right after that, with probability 1/2 if I pick a total of 2 items, 1/3 if 3 three items ... and 1/n if n items. So, at step n, I retain the current item with probability n/(n+1) and replace otherwise.

Post a Comment