Friday, April 1, 2011

How can you get a fair coin toss

Interview question: How can you get a fair coin toss if someone hands you a coin that is weighted to come up heads more often than tails?

The story of these types of questions starts at the software giant Microsoft who pioneered the use of puzzle type question, where the aim is to test the interviewers problem solving skills and creativity. It's ironic that these type of questions are no longer asked in Microsoft job interviews, but the rest of the software industry hasn't caught on.



The solution is to toss the coin twice, which gives four possible outcomes:
H (heads) followed by H, probability of this is pH * pH
H followed by T (tails), probability of this is pH * pT
T followed by H, probability of this is pT * pH
T followed by H, probability of this is pT * pT
Looking at the above outcomes we can see that HT (H followed by T) is just as likely as TH,
So to get a fain coin toss, toss the coins and use HT or TH as fair outcomes of the toss, and discard the results of TT and HH.

No comments: