Return 0, 1 and 2 with equal probability using the specified function

Write an algorithm to generate 0, 1 and 2 with equal probability using a specified function which either produces 0 or 1 with 50% probability each.


 

Lets say the specified function is random() which generates 0 or 1 with 50% probability each. Then if we make two different calls to the random() function and store the result in two variables, say x and y, then their sum (x + y) can be any of { 0, 1, 2 }. Here the probability of getting 0 and 2 is 25% each and probability of getting 1 is 50%.

Now the problem reduces to decreasing the probability of getting 1 from 50% to 25%. We can easily do so by forcing our function to never generate either (x = 1, y = 0) or (x = 0, y = 1) which causes the sum to be equal to 1.

 

Download   Run Code

Output (will vary):

0 ~ 33.385000%, 1 ~ 33.411000%, 2 ~ 33.204000%

 

Another plausible way of generating 0, 1 and 2 with equal probability is to use the expression 2*random() + random() which generates 0, 1, 2, 3, all with the equal probability. Now similar to the previous approach, if we make the probability of getting 3 from 25% to 0%, then the function returns returns 0, 1, and 2 with 25% probability.

 

Download   Run Code

Output (will vary):

0 ~ 33.230000%, 1 ~ 33.126000%, 2 ~ 33.644000%

 
Author: Aditya Goel

 
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