Past exam of the mathematics course of the University of Cambridge / 2026 / ia / Paper 2 / 11F / b

At time $T_k$ the visited vertices form a contiguous arc and the walk is at an endpoint. Exiting an interval of $k$ visited vertices, starting one step from an absorbing endpoint, has mean $k$. Therefore $\mathbb{E}(T_{k+1}-T_k)=k$ and $\mathbb{E}{T}_n={\sum }_{k=1}^{n-1}k=n(n-1)/2$.

For each $j\ne 0$, cut the cycle at $j$. The event that $j$ is last is the event that the lifted walk covers the other $n-1$ residues before crossing that cut. Gambler’s ruin (or cyclic symmetry of the two expanding endpoints) gives $\mathbb{P}(Z=j)=1/(n-1)$.