I'm unable to solve this. Two players, A and B alternatively toss a fair coin (A tosses the coin first, then B tosses the coin, then A, then B and so on). The sequence of heads and tails is recorded. If there is a head followed by a tail (HT sub-sequence), the game ends and the person who tosses the tail wins. What is the probability that A wins the game?


You can do this by enumerating paths, but I find it easier to think about states and recurrences.

Step 1: An easier question is to compute the probability that $A$ throws the first $T$? Call the answer $P_T$. To compute it consider the first toss. Either $A$ throws a $T$ (an instant win) or $A$ throws an $H$ in which case we are back at the start of the game only now $B$ is the first to throw, hence the probability that $A$ wins from there is ($1-P_T$). Thus:

$$P_T=\frac 12 1 + \frac 12 (1-P_T)\;\Rightarrow\;P_T=\frac 23$$

Step 2: Back to your game. Let $P$ be the answer you seek. look at the first two throws. With equal probability the players get $HH$, $HT$, $TH$, and $TT$. The first and third cases leave $A$ in the state we considered in Step 1. The second is a loss. The fourth just gets back to the initial state. Thus:

$$P=\frac 14\;\left(\frac 23 +0+\frac23+P\right)\;\Rightarrow\;P=\frac49$$

  • 1
    $\begingroup$ To make this elegant answer even more elegant, you could do step $2$ in the same style as step $1$: $A$ throws $H$ or $T$; $B$ wins with probability $P_T$ in the first case and $P$ in the second, so $$ P=1-\frac12(P_T+P) \;\Rightarrow\;\frac32P=\frac23\;\Rightarrow\;P=\frac49\;. $$ $\endgroup$ – joriki Aug 31 '15 at 8:33
  • 2
    $\begingroup$ @joriki Thanks! As yet a third variant: A has two ways of winning. Either A throws the first $H$ (prob = $\frac 23$ and then also throws the next $T$ despite starting second (prob = $\frac 13$), or $B$ throws the first $H$ ($\frac 13$) and then $A$ throws the next $T$ ($\frac 23$), hence $$P=\frac 23\,\frac 13\;+\;\frac 13\,\frac 23=\frac 49$$ $\endgroup$ – lulu Aug 31 '15 at 10:38
  • $\begingroup$ @lulu Thank you. However, can I just ask what you mean by "The first and third cases leave A in the state we considered in Step 1."? I can't see how $HH$ leaves A in the same state as Step 1. $\endgroup$ – Jojo Aug 31 '15 at 12:23
  • 1
    $\begingroup$ Sure. Given that they have thrown $HH$ (or $TH$ for that matter) then the winner will now be the first player to throw a $T$, just as in Step 1. As $A$ is the first to throw (in these two scenarios) we are exactly in the world contemplated by Step 1. (Note: the two other variants described in the comments here both avoid this line of reasoning, may give a different perspective on things). $\endgroup$ – lulu Aug 31 '15 at 12:34
  • 1
    $\begingroup$ @Jojo The probability that $A$ wins from the $TH$ scenario is the probability that $A$ throws the NEXT $T$. That leaves us in Step 1, again. Doesn't matter what came before. The probability that $A$ throws the next $T$, given that $A$ gets to go first, is $P_T$ again. $\endgroup$ – lulu Aug 31 '15 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.