Random number challenge

Corey Edwards tensai at zmonkey.org
Fri Jun 27 10:29:07 MDT 2008


On Fri, 2008-06-27 at 09:06 -0600, Jacob Fugal wrote:
> On Fri, Jun 27, 2008 at 2:03 AM, Corey Edwards <tensai at zmonkey.org> wrote:
> >> Everybody counts off 1-$MAX
> >> Flip a coin, Heads sets the bit, tails is a blank bit.
> >> Flip until you have the bits necessary to represent $MAX
> >> Congrats, you have a number for the winner of the first item.
> >
> > Something about that method just didn't sit right with me. Seemed like
> > some numbers would come out more often than others. So I sat down and
> > coded up a simulator to see if I was right. According to my results,
> > this particular distribution method unfairly favors some numbers
> > whenever the sample size ($MAX) is not an even multiple of 2 (2, 4, 8,
> > etc.).
> >
> > I've attached my simulator. Here are a couple of simple examples which I
> > think will illustrate the point:
> 
> <snip>
> 
> Woah woah woah. You're not using the technique that was advocated.
> What Hans and Jason were referring to is flip *all* the coins. If the
> full result is outside the range, reflip *all* the coins. In your
> implementation, you only reflip the most recent coin when the result
> is out of bounds. There's a big difference.
> 
> Here's a sketch of a proof for the uniformity of the distribution
> where you always reflip all the coins:
> 
> Assume the valid range is 0..6 (7 people). We flip 3 fair coins
> (ceiling of log base 2 of 7) to get a uniform distribution among 0..7,
> each number having probability 1/8. If the result is 7 (outside the
> valid range), we reflip all coins.

Having not experienced the bit flipping in person I was going just based
on the description which apparently wasn't complete. Guess I'll just
have to berate Jayce^ for a poor description. But with the reflipping of
all coins whenever an impossible number is selected, yeah that makes
sense. Thanks for clarifying. It was a fun exercise.

Corey

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://plug.org/pipermail/plug/attachments/20080627/356b3202/attachment.bin 


More information about the PLUG mailing list