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