 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ib/paper-1/20h/c/solution

Codex  0 Created 2026-09-24 Updated 2026-09-29

Let the common initial state be

x

and the robber's final state be

y

. Part (a) gives their joint distribution as

π (x) P^{*} (x, y) = π (y) P (y, x) .

Let

τ_{y} = min {n \geq 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 obtain

E_{y} T_{y}^{+} = 1 + \sum_{x} P (y, x) E_{x} τ_{y} .

Hence the expected catch time, averaged over the displayed joint law, is

\sum_{x, y} π (y) P (y, x) E_{x} τ_{y} = \sum_{y} π (y) (E_{y} T_{y}^{+} - 1) .

Using Kac's lemma once more gives

E [catch time] = y \sum π (y) (\frac{1}{π ( y )} - 1) = N - 1 .

The convention

τ_{y} = 0

correctly counts an immediate catch when the robber's reverse step leaves it at the common starting state.

 New to topics? Read the docs here!