We toss a fair coin and record the outcome as a sequence of H and T. Let $X$ be the number of tosses till $HTH$ (heads immediately followed by tails immediately followed by heads) appear for the first time. Find $\mathbb{E}(X)$.
My Work
For $X$ tosses, if $X=0,1$ then the $\mathbb{E}(X)=0$, right?
For $X>2$ Let $I_k=\begin{cases} 1 \quad \text{if we get } HTH \\ 0 \quad \text{o.w.} \end{cases}$
Then the $\mathbb{E}(X)=X*\frac{1}{8}$?
We can be in one of 3 states:
We are at least 3 filps away from completing the $HTH$ sequence. Either we have just started, or the last two flips were TT.
We are potentially two flips from completing the sequence. The last flip was a heads
Our last two flips were $HT$ and we are one flip away.
Let A be the expected number of flips from being in the first condition to completing the game, B be the expected number of flips from being in the second condition to completing the game, B be the expected number of flips from being in the third condition to completing the game
If we are in the 3rd state with 50% likelihood we complete on the next flip. With 50% likelihood we move to the first state in the next filp
$C = \frac 12 + \frac12 (A+1)$
Using similar logic we can generate these two equations.
$A = \frac 12 (B+1) + \frac12 (A+1)\\ B = \frac 12 (C+1)+ \frac12 (B+1)$
This gives us a system of linear equations. Solve and find $A$