Generate Fair Results from a Biased Coin

In this post, we will discuss how to generate fair results from a biased coin which prefer one side of the coin over another, and returns TAILS with p probability and HEADS with (1-p) probability where p != (1-p).

 

We can use the given biased coin for fair results by making two calls from biased coin instead of one call. Then if the results of both calls match (both are HEADS, or both are TAILS), we discard the results, and start over. If the results differ, we consider the first result.

 

How this works?

Suppose we have biased() function that returns TAILS with p probability and HEADS with 1-p probability. We make two independent subsequent calls to the biased() and store the results. Then there are four possible possibilities:

  1. Probability that both calls returns TAILS = p * p
     
  2. Probability that both calls returns HEADS = (1 - p) * (1 - p)
     
  3. Probability that first call returns TAILS, and the second call returns HEADS = p * (1 - p)
     
  4. Probability that first call returns HEADS, and the second call returns TAILS = (1 - p) * p

 
Clearly, the biased coin has same probability of getting TAILS and then HEADS as the probability of getting HEADS and then TAILS. So if we exclude the events of two HEADS and two TAILS by repeating the procedure, we’re left with the only two remaining outcomes having equivalent probability. That’s the reason why we will get a fair result.

 

Download   Run Code

Output (will vary):

HEADS ~ 50.237000%
TAILS ~ 49.763000%

 
References: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin

 
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