How many steps are required for the pattern 0-0-1-1.. So I'm doing this exercise where it is asked to find the number of steps in order to get the pattern 0-0-1-1
A sequence of 0s and 1s is generated by a Markov chain with transition matrix:
$$
P=    \begin{pmatrix}
    1/4 & 3/4 \\
    3/4 & 1/4  \\
    \end{pmatrix}
$$
 with states 0,1.
The first element of the sequence is decided by a fair coin flip. On average, how many steps are required for the pattern 0-0-1-1 to first appear?
I was thinking about using conditional expectation but I'm finding that it's getting too long. Is there a quick way to find the answer?
 A: The quick way is to consider a related Markov chain with 5 states: $$\{ \varnothing, 0, 00, 001, 0011\}$$ representing the portion of the pattern that's been reached so far. (A not-quite-obvious observation is that in state $\varnothing$, the last coinflip is a $1$, which affects transition probabilities.)
Let $H_{\varnothing}$, $H_0$, $H_{00}$, $H_{001}$ denote the hitting times until we reach state $0011$. Then we want to solve the system
\begin{align}
    H_{\varnothing} &= 1 + \frac14 H_{\varnothing} + \frac34 H_0 \\
    H_0 &= 1 + \frac34 H_{\varnothing} + \frac14 H_{00} \\
    H_{00} &= 1 + \frac14 H_{00} + \frac34 H_{001} \\
    H_{001} &= 1 + \frac14 (0) + \frac34 H_0
\end{align}
and compute $\frac12 H_{\varnothing} + \frac12 H_0$.
This is a bit sped up by the substitution $H_i' = H_i - H_\varnothing$, after which (subtracting $H_\varnothing$ from both sides of each equation) we get
\begin{align}
    0 &= 1 + \frac14 (0) + \frac34 H_0' \\
    H_0' &= 1 + \frac34 (0) + \frac14 H_{00}' \\
    H_{00}' &= 1 + \frac14 H_{00}' + \frac34 H_{001}' \\
    H_{001}' &= 1 + \frac14 (-H_\varnothing) + \frac34 H_0'.
\end{align}
Now we can solve for $H_0', H_{00}', H_{001}', H_\varnothing$ in that order from each equation.
