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?
0
$\begingroup$
$\endgroup$
3
$\begingroup$
$\endgroup$
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
