How many flips would it take to obtain the sequence HTHT when flipping a coin

Question

I keep on getting 25 when I compute

$$E(X) = 4(\frac{1}{2})^4 + \frac{1}{2}(1+E(X)) + (\frac{1}{2}^2)(1+E(X)) + (\frac{1}{2}^3)(3+E(X)) + (\frac{1}{2}^4)(3+E(X)) $$

Answer 1

Let states be enumerated for $\phi$, H, HT, HTH, and HTHT, solving for expected number of flips from the given state. Write the state transition equations as

$$ \tau_0 = \frac12\tau_0 + \frac12\tau_1 + 1 \\ \tau_1 = \frac12\tau_1 + \frac12\tau_2 + 1 \\ \tau_2 = \frac12\tau_0 + \frac12\tau_3 + 1 \\ \tau_3 = \frac12\tau_1 + \frac12\tau_4 + 1 \\ $$

Since $\tau_4 = 0$, this can be simplified to

$ X = \begin{pmatrix} 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ -1 & 0 & 2 & -1 \\ 0 & -1 & 0 & 2 \\ \end{pmatrix} $

solve $X^{-1}[2 \; 2 \; 2 \;2]^T$ for each given state.
$$X^{-1} = \begin{pmatrix} 3 & 4 & 2 & 1 \\ 2 & 4 & 2 & 1 \\ 2 & 3 & 2 & 1 \\ 1 & 2 & 1 & 1 \\ \end{pmatrix} $$

and the expected number of flips are [20, 18, 16, 10]. That is from initial state it will take 20 flips. Starting from H will be 18.