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.

Just make a function that calls the random number generator to return a random number form 1 to 37, twice until the numbers that add to 38 are returned. The first number to be returned is the number that was chosen randomly.

The chance for a number x to be chosen by the function is the same as the chance that the random number generator chooses x and a number (38-x) and that is equal to 1/(2 ^(38x-x^2)) . Whether x is 1, 37 or anything in between.

Posted by Max on 2004-06-08 13:40:33