Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 1 / 26I / vi / Solution

Write $q_{ij}=c{m}_{ij}$ for $i\ne j$, with a common positive constant $c$, and put $d_i={\sum }_{j\ne i}{m}_{ij}$. The infinitesimal generator matrix is symmetric because the graph is undirected. Thus the uniform distribution ${\pi }_i=1/|I|$ satisfies detailed balance, and the continuous-time random walk is reversible when started uniformly.

Its jump chain chooses a link uniformly from those incident to its current vertex:The flux ${\hat{\pi }}_i{\hat{P}}_{ij}=m_{ij}/{\sum }_j{d}_j$ is symmetric, so this random walk on a multigraph is also reversible. The continuous-time equilibrium is uniform because higher-degree vertices have shorter holding times; at jump times the equilibrium is degree-weighted. If the intended proportionality constant depends on the starting vertex, $q_{ij}=c_i{m}_{ij}$, reversibility still holds with ${\pi }_i\propto 1/c_i$, and the same jump chain results.