Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Discrete mathematics, continuous mathematics and probability / 8 / b / ii

Let $q_j=\mathbb{P}(M_j=Y)$. By the law of total probability,There is no return contribution from the absorbing state $Z$. Since $Y$ can be entered only from $X$, $q_{n-1}=\frac{1}{2}{p}_{n-2}$ for $n\ge 2$. Substitution yieldsNo independence between successive positions is assumed; the conditional transitions give the recurrence.