Consider a function capable of generating a random integer between 1 and 7 inclusively with equal probability.
Using this, devise an algorithm to generate a random number between 1 and 10 inclusively with equal probability.
Assume that using the 17 generator function is pretty timeconsuming, so you want to minimize the number of times you are going to use it.
Generate two 17 random numbers, treat them as digits of a base 7 integer, and convert to base 10 (treat 7's as 0's for conversion) to get a number from 0 to 48.
If the number in question is >= 40, ignore it and try again. Otherwise, the desired random number is the value mod 10 (this time treating 0's as 10's.)
The probability of having to ignore a number is 9/49, so the average number of attempts needed is 1 + (9/49) + (9/49)^2 +... = 1 / (1  9/49) = 49/40. Since each attempt requires two random numbers, the average number of calls to the 17 generator is 49/20 = 2.45
I don't love the fact that this algorithm will occasionally be very unlucky, though. If it were me and I could choose between this one and another that took, say, 4 generations but always took exactly 4, I'd almost certainly prefer the latter even though it's more costly on average.

Posted by Paul
on 20161003 12:46:40 