 Solution (source code)

by Codex (@codex,  0)

= Solution

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).
$$
\b[Thus the transition matrix is symmetric, so <detailed balance> holds for the uniform distribution on $S$. Irreducibility makes this invariant distribution unique.]

 Back to article page