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

A partition of a set consists of nonempty subsets that are pairwise disjoint and whose union is the whole set. HereThus every outcome belongs to exactly one cell. The probability calculation additionally requires the cells to be measurable events.

For a finite or countable measurable partition, the law of total probability isIndeed, $A$ is the disjoint union of $A\cap B_i$, and the conditional probability formula gives each positive-probability term. Zero-probability cells contribute zero; their conditionals need not be defined by a ratio. If all cells have positive probability, the sum simply runs over every $i\in I$.

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.