Past exam of the mathematics course of the University of Cambridge / 2019 / ib / Paper 1 / 20H (Markov Chains)

By the definition of conditional probability and stationarity,This is the transition matrix of the time-reversed Markov chain.

Conditional on $X_0=x$, the random variable $T$ is the first return time $T_x^{+}$. The Kac's lemma mean-recurrence formula for a finite irreducible Markov chain givesAveraging over $X_0\sim \pi$ therefore yields

Let the common initial state be $x$ and the robber's final state be $y$. Part (a) gives their joint distribution asLet ${\tau }_y=\min \{n\ge 0:X_n=y\}$ be the cop's hitting time of $y$ when starting from $x$. For a chain started from $y$, condition on its first step to obtainHence the expected catch time, averaged over the displayed joint law, isUsing Kac's lemma once more givesThe convention ${\tau }_y=0$ correctly counts an immediate catch when the robber's reverse step leaves it at the common starting state.