A cute probability problem
I’ve got a lot to do today, so I’ll restrict myself to a very quick post in the series marked Cute Problems. This one is to do with probability.
Two people (A and B) play a game which involves a sequence of tosses of a coin. The coin is “fair” so that the probability of a Head (H) is 0.5, equal to the probability of a Tail (T). Successive tosses of the coin are independent.
The game ends when two successive tosses show either the sequence HT (in which case Player A wins) or the sequence TT (in which case Player B wins). If neither pairing is seen the coin is tossed again and again until either HT or TT is seen.
What is the probability that Player A wins?
Answers (with explanations please) through the comments box..
Follow @telescoper
In the Dark 
October 20, 2013 at 11:20 am
since “the game ends when two successive tosses show either ….. ”
…. surely it depends on who throws first ?
October 20, 2013 at 11:29 am
No. There is only one coin. It doesn’t matter who throws it if it is tossed fairly.
October 20, 2013 at 11:53 am
My instinct is that there is a 50/50 chance for A and B to win. (Given 2 throws, HT and TT are two of the outcomes, (TH and HH being the others) and so seem equally likely.)
However, my learned response to the title “cute probability problem” is that my instinct is wrong…
October 20, 2013 at 12:20 pm
You are correct in your assessment that your instinct is wrong.
October 20, 2013 at 12:44 pm
I thought that at first too. But then I realised: imagine the coin comes up H. Then there is a 50% chance for A to win on the next coin toss. If he fails, the the next toss still gives him a 50% chance to win.
On the other hand, if the coin comes up T, there is a 50% chance for B to win the next toss. But if he fails, the next toss gives his opponent a chance to win. So clearly the situation is asymmetric and player A is more likely to win.
I haven’t worked out how to do the calculation yet.
October 20, 2013 at 12:44 pm
The first two tosses can be:
HH, HT, TH, TT
Straightforwardly, HT leads to A winning and TT to B
HH will always lead to A winning, since as soon as a T is tossed, A wins.
Likewise TH. If a T is tossed next, A wins, if an H, it is like the HH situation. A wins eventually.
Hence, P(A wins) = 3/4
October 20, 2013 at 12:53 pm
If the previous toss was an H, then A has a 50% chance to win, and a 50% chance for the game to continue. But eventually he will win – there is no way for TT to occur without it being the sequence HTT and player A winning.
So it all comes down to the first toss – if T comes up, B has a 50/50 shot at winning there and then. Otherwise H wins. If H comes up, A wins.
So it’s a 25% chance of B winning, 75% of A winning.
Is this right?
October 20, 2013 at 12:54 pm
Ah, crossposted with Paul!
October 20, 2013 at 4:26 pm
Yes, the only way B can win is to throw TT off the top. All other possibilities require the sequence HT to occur before TT can. The answer is therefore 1/4 for B and 3/4 for A.
I first came across this puzzle in a lecture about genetics as a warm-up for much more complicated problems arising from DNA sequences.
The reason why intuition fails here is that although individual tosses are independent, the first member of each new pair contains the second member of its predecessor, so that pairs are not independent. This is also why a sequence of moving averages over a sequence of uncorrelated variables is correlated.
October 20, 2013 at 8:32 pm
Cute indeed! I like that all the key insights leading to the solution are qualitative, with just a single quantitative calculation at the end:
– If ever an H is rolled, A will win as long as the game terminates.
– The game terminates with probability 1.
– The game can’t end on the first toss.
* By the second toss, there are four equally probable histories, and the only one in which an H has never been rolled is the one in which B wins immediately.
October 20, 2013 at 8:34 pm
Whoops… the last A in my comment above should be a B. Perhaps a moderator could edit it for me? *bats eyelashes*
October 20, 2013 at 8:43 pm
That’s the correct way to ask for an amendment to be made.
October 21, 2013 at 3:08 pm
Clearly the only TT not preceded by an H is if the first two
tosses are tails. So 0.25 chance for B to win
October 21, 2013 at 3:51 pm
Used this in tutorials today with some success. Thanks.
October 22, 2013 at 2:13 pm
I get 0.75 as the analytic answer for A’s likelihood of winning and my python simulation suggests a similar result. I could send you the code if you want (assuming I’m right).
October 22, 2013 at 2:25 pm
See the above.
October 22, 2013 at 2:27 pm
Nice one – a good one for showing how drawing a diagram of the options helps. š There only 25% chance of a TT ending (as all other options get stuck on H first so can only end in HT). So A wins 75% of the time…. Could it be a metaphor for other seemingly fair selection procedures?