Random number challenge

[Hans Fugal]

Jacob Fugal wrote:

> 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.

Exactly. Allow me to quote myself: "Or do you mean a way without a 
computer? In that case grab lg(N) people and have them each flip a coin, 
repeat if you get a number bigger than N. Expected number of trials is 
between 1 and 2."

>>From a practical standpoint, the probability of having to reflip more
> than a few times depends on the number of people in the room. If you
> have (2^N)+1 people in the room, your chances of having to reflip are
> the worst at 0.5 - 1/2^(N+1). For most N, this is pretty close to 50%
> and you may have to reflip several times to get a valid winner. On the
> other hand, if you have (2^N)-1 people in the room, your chances of
> having to reflip are very low, in which case this technique works very
> well.

Which actually translates to an expected value of 2 flips before you get 
a usable number.

I wrote a little empirical proof to go along with your theory. Here's 
what it looks like:

$ ./flips.rb 17
   0: ***********************************************************
   1: ***********************************************************
   2: ***********************************************************
   3: ***********************************************************
   4: **********************************************************
   5: ***********************************************************
   6: ***********************************************************
   7: ***********************************************************
   8: ***********************************************************
   9: ***********************************************************
  10: **********************************************************
  11: ***********************************************************
  12: ***********************************************************
  13: ***********************************************************
  14: ***********************************************************
  15: ***********************************************************
  16: **********************************************************
Average reflips per prize: 0.880561

Script is attached.


-- 
Hans Fugal ; http://hans.fugal.net

There's nothing remarkable about it. All one has to do is hit the
right keys at the right time and the instrument plays itself.
     -- Johann Sebastian Bach
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: flips.rb
Url: http://plug.org/pipermail/plug/attachments/20080627/3e4919ae/attachment.pl