Generate numbers from 1 to 7 with equal probability using specified function

Write an algorithm to generate numbers from 1 to 7 with equal probability using a specified function which produces random numbers between 1 to 5 with equal probability.


 

Suppose the specified function is random() which generates random numbers from 1 to 5 with equal probability. The idea is to use the expression 5*(random() - 1) + random() which uniformly produces random numbers in range [1-25]. So if we exclude the possibility of the random number being one among [8-25] by repeating the procedure, we’re left with numbers between [1-7] having equivalent probability.

 

How this works?

Since random() returns random numbers from 1 to 5 with equal probability, R = 5*(random() - 1) can be any of 0, 5, 10, 15 or 20. Now for the second random() call, let’s explore all possibilities:


If R=0R + random() can be any of 1, 2, 3, 4, 5
If R=5R + random() can be any of 6, 7, 8, 9, 10
If R=10R + random() can be any of 11, 12, 13, 14, 15
If R=15R + random() can be any of 15, 16, 17, 18, 19, 20
If R=20R + random() can be any of 21, 22, 23, 24, 25

 

So the expression uniformly distributes the numbers in range [1-25].

 

Download   Run Code

Output (will vary):

1 ~ 14.29%
2 ~ 14.25%
3 ~ 14.33%
4 ~ 14.27%
5 ~ 14.26%
6 ~ 14.31%
7 ~ 14.29%

 

In order to minimize the number of calls to the random() function, we can make the while loop stop at r <= 21 and use modulo operator as shown below:

 

 

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz