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?
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.