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

A partition of a set $\Omega$ is a collection of nonempty subsets whose union is $\Omega$ and which are pairwise disjoint:For use with probabilities, the $B_i$ must also be events in the sample space.

For a finite or countable partition of a set into events $B_i$, the law of total probability statesThe events $A\cap B_i$ are pairwise disjoint and have union $A$, so countable additivity proves the formula. Terms with $\mathbb{P}(B_i)=0$ contribute zero and are omitted to avoid undefined conditional probabilities.

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.