Can anyone help me with this?
A sequence of 0’s and 1’s is generated by a Markov chain with transition matrix
P= \begin{pmatrix} 1/4 & 3/4 \\ 3/4 & 1/4 \\ \end{pmatrix}
and the first element of the sequence is decided by a fair coin toss. On average, how many steps are required for the pattern 0; 0; 1 to first appear?
I am thinking of using conditional expectation but i dont know how.
Let $E_{00}$ be the expected number of additional steps needed to reach $0, 0, 1$ if the last two steps were $0,0$, let $E_0$ be the expected number of additional steps needed to reach $0, 0, 1$ if the last step was $0$, but the last two were not $0, 0$. And let $E_1$ be the expected number of additional steps needed to reach $0, 0, 1$ if the last step was not a $0$.
Then we have, by conditional expectation, that $$ E_{00} = \frac34\cdot 1 + \frac14(1 + E_{00})\\ E_{0} = \frac34(1 + E_1) + \frac14(1+E_{00})\\ E_1 = \frac14(1+E_1) + \frac34(1+E_0) $$ They give the result $$ E_{00} = \frac43\\ E_{0} = \frac{28}3\\ E_1 = \frac{32}3 $$ And, since you use a coin toss to decide whether you start at $E_0$ or at $E_1$, the total expected number of steps is therefore $$ \frac{\frac{28}3 + \frac{32}3}{2} = 10 $$