A particular random number generator returns positive integer n with probability 1/(2^n). (ie '1' with probability 1/2, '2' with probability 1/4, '3' with probability 1/8, etc.)

Using this random number generator, write an algorithm which chooses a random integer from 1 to 37 with equal probability.

Charlie's program got me thinking that I was giong about this all wrong and I came up with a new idea...

Using two pointers, one for the upper end of values and one for the lower end of values I retrieve a number from the Weighted_Random_Number_Generator.  If the returned value is 1, then I move the upper pointer down to halfway between the previous upper and lower pointer values, if it is something other than 1 I move the lower pointer up to halfway between the upper and lower pointers.  When the pointers meet, I return that value.

It works pretty well, but for some reason 1 and 37 are returned only half as often as expected.  Here's the code:

Function Random2()
 
Dim Pointer1, Pointer2, IntArray(37) As Integer
 
Pointer1 = 1
Pointer2 = 37
 
While Pointer1 < Pointer2
    If Random37() = 1 Then
        Pointer2 = (Pointer1 + Pointer2) / 2
    Else
        Pointer1 = (Pointer1 + Pointer2) / 2
    End If
Wend
 
Random2 = Pointer2
 
End Function

...and here are the results after 100,000 runs:

  1  .01406-   2  .02708-   3  .02799-   4  .02785-   5  .02734-   6  .0273-   7  .02658-   8  .02783-   9  .0284-   10  .02854-   11  .02798-   12  .02753-   13  .02844-   14  .02697-   15  .02887-   16  .02776-   17  .02691-   18  .02775-   19  .02724-   20  .02841-   21  .02779-   22  .02889-   23  .02776-   24  .0281-   25  .02747-   26  .02711-   27  .02747-   28  .02722-   29  .02768-   30  .02722-   31  .02858-   32  .02834-   33  .02738-   34  .02842-   35  .02804-   36  .0273-   37  .0144-

The expected value is 0.027027...

Posted by Erik O. on 2004-06-08 16:29:15