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 1-7 generator function is pretty time-consuming, so you want to minimize the number of times you are going to use it.
Generate two 1-7 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 1-7 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 2016-10-03 12:46:40 |
One approach
