Each Friday, the ever-entertaining Professor Richard Wiseman poses on his blog a problem for readers to solve. He posts the solution on Monday.
(Wiseman is at the University of Hertfordshire in England, so watch out if you are several time zones away. And while I am on the subject of not living in England, Hertfordshire is pronounced “hart-fud-shuh” not “hert-ford-shyer”. A completely understandable error for Americans and Canadians.)
On July 6 (2012), he posted the following:
John wants to toss a coin to make a random decision.
However, he only has a biased coin (that is, a coin that does not have a 50:50 chance of coming up heads or tails). Even worse, John doesn’t know the extent of the bias, and thus has no idea about the likelihood of obtaining a head or tail.
How can John toss the coin to make a 50:50 random decision?
Stop reading now if you want to try to solve the problem. My solution coming up. I am writing this on July 8 and will not post it until after Wiseman has revealed his solution on July 9. His solution may not be the same as mine.
Name the two choices Option 1 and Option 2. John tosses the coin twice. If he gets HH or TT, he discards the result and does another pair of tosses. He does this until he gets H followed by T or T followed by H. Call this a “mixed” result. If the mixed result is HT he chooses Option 1; if it’s TH, he chooses Option 2.
For example, the following sequences lead to Option 1: HT, or (HH)(TT)HT, or (TT)(HH)(HH)HT. And if he gets TH, or (TT)TH, or (TT)(HH)(TT)TH he goes for Option 2. I’ve put brackets around the pairs of results he discards.
You can of course check out that this leads to equal chances for the two options by doing a few trials with an unbiased coin, but if you really want to test it, use a die. If the die comes up 6, count that as tails; numbers 1 to 5 count as heads. So, for example, 5, 1, 4, 4, 2, 6 counts as HHHHHT (go for Option 1) and 1,3,6,1 counts as HHTH (Option 2). What you have here is a very biased “coin”. But you should get Option 1 about the same rate as Option 2.
Remember — the tosses have to come in pairs, so something like HHT is an incomplete sequence — toss again.
Why it works
Knowing a bit of elementary probability theory will help you here.
Suppose the probability of heads is P(H) = p and the probability of tails is P(T)=1-p = q. Then
But the conditional probabilities of HT and TH are
And that’s exactly the probability we want.
Suppose John has three or four or even n options. Can you generalize the method to accommodate him? The answer is left, as the mathematics text books say, as an exercise for the reader. Answer later today (July 9) or tomorrow, depending on how my time shakes down.