All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Random Trial (Posted on 2016-10-02)
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.

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 One approach | Comment 2 of 3 |
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

 Search: Search body:
Forums (0)