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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of