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

Starting at $X$, the two possible two-step returns are $X\to X\to X$ and $X\to Y\to X$. They are disjoint events, with probabilities $1/4$ and $3/16$. ThereforeEach path probability uses the specified Markov property to multiply its successive transition probabilities.

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.

The initial values are $p_0=1$ and $p_1=1/2$. The characteristic polynomial of the linear recurrence iswith roots $3/4$ and $-1/4$. Hence $p_n=a(3/4{)}^n+b(-1/4{)}^n$. The initial conditions give $a+b=1$, $3a-b=2$, so $a=3/4$, $b=1/4$. Therefore

The Markov property and time homogeneity giveSince $p_{2n}>0$, conditional probability yields the Markov chain return bridge expressionThe explicit formula gives $p_n\sim \frac{3}{4}(3/4{)}^n$, soThe conditioning event has positive probability at each finite time even though those return probabilities tend to zero. Taking an undefined conditional on an infinite-time zero-probability event is not needed.