Past exam of the mathematics course of the University of Oxford / 2017 / Prelims / Mathematics III / 5 / b

There are two paths from $X$ back to $X$ in two steps: $X\to X\to X$ and $X\to Y\to X$. By the markov property, their probabilities multiply along each path. Therefore

Let $q_n=\mathbb{P}(M_n=Y)$. The law of total probability applied to the current markov chain state givesThe second equality holds because $Y$ can only be reached from $X$. Eliminating $q_{n-1}$ gives the linear recurrence relation

The characteristic equation of a linear recurrence isIts distinct roots are $3/4$ and $-1/4$, so $p_n=A(3/4{)}^n+B(-1/4{)}^n$. The initial conditions are $p_0=1$ and $p_1=1/2$, giving $A+B=1$ and $3A-B=2$. Hence $A=3/4$, $B=1/4$, and

Starting from $X$ at time $n$, the markov property and the time-independent transition rules give $\mathbb{P}(M_{2n}=X\mid M_n=X)=p_n$. ThereforeWrite $p_n=\frac{3}{4}(\frac{3}{4}{)}^n\left(1+\frac{1}{3}(-\frac{1}{3}{)}^n\right)$. The conditional probability becomesThe conditioning selects paths which have avoided the absorbing state up to time $2n$; it is therefore quite different from the unconditioned probability $p_n$, which tends to zero.