I am tossing a coin with probability $p$ of heads (H) and $q=1-p$ of tails (T). What is the expected number of tosses until I get HTH?
The book that I am reading suggests the following solution: consider the event that HTH does not occur in $n$ tosses, and in addition the next three tosses give HTH. If we look at the combinations of the $(n-1)$-th and $n$-th tosses, followed by HTH, we can deduce that:
\begin{equation}
\mathbb{P}(Y>n)p^2q=\mathbb{P}(Y=n+1)pq+\mathbb{P}(Y=n+3),\quad n\geq 2
\end{equation}
As suggested, it is possible to sum this equation over $n$ in order to obtain that $\mathbb{E}(Y)=(pq+1)/(p^2q)$. However, I tried to do the sum and manipulate it in different ways but I could not obtain anything that leads me to this conclusion.
Best Answer
The method I like for this kind of problem is to set up a Markov chain. Here the state space is the last three coin flips that we saw. We set the initial distribution to be the usual distribution on 3 biased coin flips (a sequence containing $k$ heads has probability $p^k q^{3-k}$). Then we use a standard "renewal argument":
$$E[\tau_{HTH} \mid X_0=i] = \sum_{j \in S} (1+E[\tau_{HTH} \mid X_0=j]) p_{ij} = 1 + \sum_{j \in S} E[\tau_{HTH} \mid X_0=j] p_{ij}$$
This is just saying that if we start at $i$, we go to a new state $j$, that takes one flip, and then we add in the average number of flips it's going to take us to get from $j$. Finally we adjoin the boundary condition $E[\tau_{HTH} \mid X_0=HTH]=0$. So one of our seven other equations will be
$$E[\tau_{HTH} \mid X_0=HHH]=1+p E[\tau_{HTH} \mid X_0=HHH]+ q E[\tau_{HTH} \mid X_0=HHT].$$
Solving this whole system of linear equations, left-multiplying the resulting column vector by the row vector of the initial distribution, and then adding $3$ (to take into account the initial three flips) gives the desired result.
This approach is quite flexible; for example it can be used to understand the surprising differences between "HHT" and "HTT".