On Fri, 2008-06-27 at 09:06 -0600, Jacob Fugal wrote: > On Fri, Jun 27, 2008 at 2:03 AM, Corey Edwards <[EMAIL PROTECTED]> 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
signature.asc
Description: This is a digitally signed message part
/* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
