Considering an infinite sequence of tosses of a fair coin, how long will it take on average until the pattern HTT appears?
I thought one way to solve this would be as a Markov Chain, where the state it is in is defined as the number of flips away from making the sequence HTT. For example, if the sequence is HTHHT, it would be in state 1, since it only needs one more flip to form HTHHTT.
I defined the state-change matrix $P_{ij}$ containing the probability of transitioning from state i to state j, where i represents the row and j represents the columns. The first row is all zeroes because after HTT (state 0) appears, the sequence ends.
$$P_{ij} =\begin{bmatrix}0 & 0 &0 &0\\1/2&0&1/2 &0\\0&1/2&1/2&0\\0&0&1/2&1/2\end{bmatrix}$$
I also defined $x_0$ as the state of the sequence at flip 0. $x_n = x_{n-1}*P_{ij}$ is the state at flip n.
$$x_0 = \begin{bmatrix}0 & 0 &0 & 1\end{bmatrix}$$
I defined $E[X]$ = $$\sum_{k=0}^{\infty} k*P(State\ 0 \ or \ HTT \ formed \ at \ flip \ k) = k * x_k(j = 0) $$
I am not getting the right answer for some reason. I know there is another way to solve this problem using martingales, but I would like if someone could point out what errors I am making in my process.
There are four states of interest, according to how much of $HTT$ is complete. Thus we have the states $\emptyset, H,HT,HTT$. Of course, the expectation from $HTT$ is $0$.
Let $E_S$ be the expectation from a given state $S$, and let the answer you want be denoted by $E=E_{\emptyset}$.
Barring arithmetic error (always possible) we see that $$E_{HT}=\frac 12\times 1 + \frac 12\times (E_H+1)$$
$$E_H=\frac 12\times (E_{HT}+1)+\frac 12\times (E_H+1)$$
Together these imply that $$E_H=6\quad \&\quad E_{HT}=4$$
Now we also have $$E=\frac 12\times (E_H+1)+\frac 12\times (E+1)\implies E=8$$