2019-46.md

course	course_year	question_number	tags	title	year
Markov Chains	IB	46	IB 2019 Markov Chains	Paper 1, Section II, H	2019

Let $P$ be a transition matrix for a Markov chain $\left(X_{n}\right)$ on a state space with $N$ elements with $N<\infty$. Assume that the Markov chain is aperiodic and irreducible and let $\pi$ be its unique invariant distribution. Assume that $X_{0} \sim \pi$.

(a) Let $P^{}(x, y)=\mathbb{P}\left[X_{0}=y \mid X_{1}=x\right]$. Show that $P^{}(x, y)=\pi(y) P(y, x) / \pi(x)$.

(b) Let $T=\min \left{n \geqslant 1: X_{n}=X_{0}\right}$. Compute $\mathbb{E}[T]$ in terms of an explicit function of $N$.

(c) Suppose that a cop and a robber start from a common state chosen from $\pi$. The robber then takes one step according to $P^{*}$ and stops. The cop then moves according to $P$ independently of the robber until the cop catches the robber (i.e., the cop visits the state occupied by the robber). Compute the expected amount of time for the cop to catch the robber.