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)
skip to main |
skip to sidebar
Mostly my random thoughts about world, universe and everything. Prepare to enter an abstract world of messed up neurons '...abandon all hopes, ye who enter here...'.
statcounter
COPYRIGHT
Anything I have used that is not mine is explicitly cited and is copyrighted by the source I obtained from. Everything else is copyrighted by me and may not be copied or used for any purpose without my explicit permission (which I give away for free when asked). Linking is allowed as per fair use.
1 comment:
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