If distinct states $X,Y$ communicate in one step, they differ by a unique removed vertex and a unique inserted vertex. Consequently
$$
P(X,Y)=\frac1{sn}=P(Y,X).
$$
Thus the transition matrix is symmetric, so <detailed balance> holds for the uniform distribution on $S$. Irreducibility makes this invariant distribution unique.

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 215 / 4 / b / ii / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-215/4/b/ii/solution