# Random number challenge

Hans Fugal hans at fugal.net
Fri Jun 27 10:39:34 MDT 2008

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