Comments on: Yoak: Pick a ball! Any Ball! http://mathfactor.uark.edu/2009/05/yoak-pick-a-ball-any-ball/ The Math Factor Podcast Site Fri, 08 Aug 2014 12:52:06 +0000 hourly 1 https://wordpress.org/?v=4.9.25 By: jyoak http://mathfactor.uark.edu/2009/05/yoak-pick-a-ball-any-ball/comment-page-1/#comment-510 Wed, 06 May 2009 19:46:22 +0000 http://mathfactor.uark.edu/?p=579#comment-510 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.

]]> By: Andy http://mathfactor.uark.edu/2009/05/yoak-pick-a-ball-any-ball/comment-page-1/#comment-509 Wed, 06 May 2009 13:39:34 +0000 http://mathfactor.uark.edu/?p=579#comment-509 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.

]]> By: Andy http://mathfactor.uark.edu/2009/05/yoak-pick-a-ball-any-ball/comment-page-1/#comment-508 Wed, 06 May 2009 13:36:40 +0000 http://mathfactor.uark.edu/?p=579#comment-508 [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]

]]>