Yoak: Pick a ball! Any Ball!
This is a quickie that came out of my computer programming work adapted as a puzzle.
I propose to stand in front of you with a bag of balls. I will hand you the balls one at a time. You have no idea how many balls my bag contains. I will also provide you with a magic device such that when its button is pushed, it provides you with a random number between 0 and 1. You may use this as often as you like.
You must hold on to exactly one ball at a time. When I hand you a ball, you must either throw it away immediately or else retain it and throw away the ball that you were previously holding. After you have either retained or thrown away the last ball, your goal is for there to be an exactly equal chance that you are currently holding each of the balls that I have handed you.
It may help to provide a similar problem to demonstrate how you might use the magical device to accomplish something similar. Suppose that I told you in advance that there were ten balls. You could then use the device to generate your random number and multiply that number by 10. This would give you a random number between 0 and 10 uniformly distributed over that range. You could then designate all numbers up to 1 as pointing to the first ball, numbers greater than 1 up to 2 as the second ball, etc. Your strategy would then be to throw away balls until handed the ball corresponding to your number and retaining that one from then on. With this strategy, you would retain each of the balls with an exactly 10% chance.
This method can’t be directly adapted to the puzzle because you wouldn’t know what multiple to use before the first draw because you don’t know how many balls will be present, so you’ll need another strategy.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Andy said,
May 6, 2009 at 7:36 am
[spoiler]
You keep the first ball. After that, for the second ball, you keep it with 1/2 probability, for the third ball you keep it with 1/3 probability, and so on. This is easy to due using the [0, 1] random number generator. For example to get 1/3 probability multiply it by 3 and check whether it is less than 1.
Now to show that this works. Let’s say there were N balls (of course you don’t know this in advance). Then the chance you keep the last ball is obviously 1/N. The chance you keep the (N-1)-st ball is 1/(N-1) times (N-1)/N, which is also 1/N. So now you can use an easy induction argument to show that the same is true for every ball.
[/spoiler]
Andy said,
May 6, 2009 at 7:39 am
Also, I wanted to point out that if there is some cost to generating the random number, there are more clever/complicated solutions which require fewer random numbers.
jyoak said,
May 6, 2009 at 1:46 pm
Thanks for that, Andy. It’s exactly what I had in mind. This came up practically where we had to grab a random item out of a stream of unknown length with uniform distribution. Though the streams weren’t ridiculously large, this was happening many times in parallel and the process was memory constrained rather than CPU constrained so generating a random number per element was preferable to storing each instance of a stream.