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

A chain is reversible with respect to $\pi$ when ${\pi }_i{P}_{ij}={\pi }_j{P}_{ji}$ for all states. For random walk on a finite connected undirected graph, ${\pi }_i=\mathrm{deg}(i)/(2|E|)$ satisfies this because both sides equal $1/(2|E|)$ on an edge and zero otherwise.

The graph has six edges, and $A$ has degree one. Hence ${\pi }_A=1/12$. Kac's return-time formula gives

After the forced first step $A\to B$, let $h_i=P_i(T_A<T_F)$. Symmetry gives $h_C=h_D=x$, whileSolving gives $h_B=2/3$. Thus the requested probability is $2/3$.

Let $g_i=E_i[T_A{1}_{\{T_A<T_F\}}]$ for the chain absorbed at $A$ or $F$. With $g_C=g_D=y$, First-step analysis givesThus $y=3$ and $g_B=8/3$. Including the initial step from $A$, the conditional mean is