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.

It's quite simple.  We first produce an algorithm to produce random numbers ranged from 1 to 2^6-64 uniformly.

The generator produce 1 with 1/2 probability and not 1 with 1/2 probability.  So if it's 1, narrow down the range to 1 to 32 with 1/2 chance and 33 to 64 to 1/2 chance.  Now run the generator again and narrow down the range by half again.  We'll need to run the generator 6 times so that the range will be limited to one number.

Now this generator will return 1-64 uniformly randomly.  If the number returned is greater than 37, simply throw it away and run it again.  The result should be a random number between 1-37 with equal chance.

Posted by Bon on 2004-08-09 13:59:21