Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Simulate random7() using random5()

Puzzle: Given a function random5() which randomly generates numbers from 1 to 5 with equal probability, write
a function random7() which generates numbers from 1 to 7 with equal probability.

Solution: Probability of any number being generated by random5() = 1/5 = 0.2
Probability of any number being generated by random7() = 1/7 = 0.14

How about random7() = 1 + (random5() + random5()) % 7

It generates numbers from 1 to 7, so functionally it's correct.

However, the numbers are not generated by equal probability.
Here is the probability of each number being generated.

Total number of ways = 5*5 = 25 (because each random() can generate any number from 1 to 5)
Output Ways to get the output Probability
1 2,5
3,4
4,3
5,2
P = 4/25 = .16
2 3,5
4,4
5,3
P = 3/25 = .12
3 1,1
4,5
5,4
P = 3/25 = .12
4 1,2
5,5
2,1
P = 3/25 = .12
5 1,3
2,2
3,1
P = 3/25 = .12
6 1,4
2,3
3,2
4,1
P = 4/25 = .16
7 1,5
2,4
3,3
4,2
5,1
P = 5/25 = .20
Total 25/25 = 1

So the probability distribution of the above function is not equal for all the numbers.
Hence it cannot be accepted as a solution.

To make the distribution equal, some other function is required.

Consider 1 + (random5()*5 + random5() - 5 )%7

The first term in the above expression would generate numbers as 5, 10, 15, 20, 25

And the last term in this expression would reduce those numbers to 0, 5, 10, 15, 20

Addition of second term would give the numbers as:

1,2,3,4,5, 6,7,8,9,10, 11,12,13,14,15, 16,17,18,19,20, 21,22,23,24,25

So we have extended the range of output from 10 to 25 numbers and since the total number of possible outputs is also 25,
this means that each of the above numbers now has equal probability P = 1/25 = .04.

On applying modulus 7 operator, this probability remains unaffected for 0 to 20

After that, the remaining numbers 21, 22, 23, 24 and 25 give an unfair advantage to 1+21%7, 1+22%7, 1+23%7, 1+24%7, 1+25%7 = 1,2,3,4,5 numbers

So if we ignore these particular outcomes, then our probability distribution remains equal for 1 to 7 numbers.

Keeping these in mind, following code can be used to get random7() from random5():
```int rand7()
{
while (true)
{
int num1To25 = rand5()*5 + rand5() - 5;
if (num1To25 < 21)
return 1 + num1To25%7;
}
return -1; // statement never reached but required for successful compilation
}
```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: