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?

17 Responses to “A cute probability problem”

1. since “the game ends when two successive tosses show either ….. ”
…. surely it depends on who throws first ?

2. AstroSpanner Says:

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…

• telescoper Says:

• 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.

3. 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

4. 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?

• Ah, crossposted with Paul!

• telescoper Says:

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.

5. 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.

6. Whoops… the last A in my comment above should be a B. Perhaps a moderator could edit it for me? *bats eyelashes*

7. 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

8. 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).

9. 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?