= Solution
Let the common initial state be $x$ and the robber's final state be $y$. Part (a) gives their joint distribution as
$$
\pi(x)P^*(x,y)=\pi(y)P(y,x).
$$
Let $\tau_y=\min\{n\geq0: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
$$
\mathbb E_yT_y^+=1+\sum_xP(y,x)\mathbb E_x\tau_y.
$$
Hence the expected catch time, averaged over the displayed joint law, is
$$
\sum_{x,y}\pi(y)P(y,x)\mathbb E_x\tau_y
=\sum_y\pi(y)\left(\mathbb E_yT_y^+-1\right).
$$
Using <Kac's lemma> once more gives
$$
\boxed{\mathbb E[\text{catch time}]
=\sum_y\pi(y)\left(\frac1{\pi(y)}-1\right)=N-1}.
$$
The convention $\tau_y=0$ correctly counts an immediate catch when the robber's reverse step leaves it at the common starting state.
Back to article page
