Reversible CTMCs on Weighted Graphs

From Edge Weights to Transition Rates

A weighted graph describes how strongly each pair of neighboring states is connected. To turn those weights into a continuous-time Markov chain, one must also specify how quickly the process leaves each state. A natural choice is to make the jump rate out of a vertex equal to one: the edge weights then determine the destination of each jump, while the holding times are exponential with mean one. For this canonical walk, stationary mass is proportional to weighted degree, and reversibility follows from symmetry of the edge weights.

Let \(G=(S,E)\) be an undirected graph with no self-loops. For each edge \(\{i,j\}\in E\), assign a finite positive conductance \(c_{ij}=c_{ji}>0\); for pairs that are not edges, set \(c_{ij}=0\). Define the weighted degree \(c_i=\sum_{j\in S}c_{ij}\), and assume \(0<c_i<\infty\) for each vertex. In the finite-graph results below, assume also that \(S\) is finite. In the countable-graph result, assume \(S\) is countable and \(C=\sum_{i\in S}c_i<\infty\).

Because there are no self-loops, \(p_{ii}=0\). Each row of \(P=(p_{ij})\) sums to one: \(\sum_jp_{ij}=\sum_jc_{ij}/c_i=1\). Each row of \(Q\) sums to zero: \(\sum_jq_{ij}=-1+\sum_{j\ne i}p_{ij}=0\). On a probability space supporting a rate-one Poisson process and an independent discrete-time Markov chain with transition matrix \(P\), define \(X_t=Y_{N_t}\). This constructs the continuous-time chain: its successive holding times are independent exponential random variables of rate one, and its successive destinations follow \(P\). The Poisson process has finitely many arrivals on every bounded time interval, so this construction is nonexplosive.

Stationary Mass and Symmetric Flux

Proof. For any \(i,j\), including \(i=j\), symmetry of the conductances gives \(\pi_i p_{ij}=c_{ij}/C=\pi_jp_{ji}\). Also, \(\pi\) is a probability distribution since its entries are nonnegative and \(\sum_i\pi_i=\sum_i c_i/C=1\). For a fixed \(j\), sum the flux identity over \(i\). In the countable case all terms are nonnegative, so the sum is well-defined and can be evaluated directly: \(\sum_i\pi_i p_{ij}=\sum_i c_{ij}/C=c_j/C=\pi_j\), using \(c_{ij}=c_{ji}\). Thus \(\pi P=\pi\). Since \(Q=P-I\), where \(I\) is the identity matrix, \(\pi Q=\pi P-\pi=0\). For this construction \(P(t)=e^{tQ}=e^{-t}\sum_{n\ge0}t^nP^n/n!\). The series converges because its nonnegative coefficients sum to one. From \(\pi P=\pi\), induction gives \(\pi P^n=\pi\) for every \(n\ge0\). Therefore \(\pi P(t)=e^{-t}\sum_{n\ge0}t^n\pi/n!=\pi\), proving stationarity in continuous time. To verify reversibility at every time, first note that \(\pi_iP_{ij}=\pi_jP_{ji}\). If this identity holds for \(P^n\), then \(\pi_iP^{n+1}_{ij}=\sum_k\pi_iP^n_{ik}P_{kj}=\sum_k\pi_kP^n_{ki}P_{kj}=\sum_k\pi_jP_{jk}P^n_{ki}=\pi_jP^{n+1}_{ji}\). The equalities use the induction hypothesis and then \(\pi_kP_{kj}=\pi_jP_{jk}\). Hence the identity holds for all powers, and the series for \(P(t)\) gives \(\pi_iP_{ij}(t)=\pi_jP_{ji}(t)\). Finally, for \(i\ne j\), \(\pi_iq_{ij}=c_{ij}/C=\pi_jq_{ji}\); for \(i=j\) the equality is automatic. This proves the claimed generator flux balance as well. \(\square\)

The quantity \(\pi_iq_{ij}\) is the stationary probability flux per unit time from \(i\) to \(j\). The theorem says that on each edge the stationary flux in one direction equals the flux in the other. The graph need not be regular: a vertex with larger total incident conductance receives more stationary mass because \(\pi_i\) is proportional to \(c_i\).

Further Graphs and a Change in Holding Rates

The degree formula depends on the choice that every vertex has total departure rate one. Conductances specify symmetric edge weights, but they do not by themselves specify holding rates. On a finite graph, one can choose positive vertex weights \(a_i\) and instead set \(q_{ij}=c_{ij}/a_i\) for \(j\ne i\), with \(q_{ii}=-\sum_{j\ne i}q_{ij}\). In that construction, \(a_iq_{ij}=c_{ij}=a_jq_{ji}\), so the stationary distribution is proportional to \(a_i\), not necessarily to \(c_i\).

Proof. The definition makes every generator row sum to zero. For distinct \(i,j\), \(\pi_iq_{ij}=(a_i/\sum_k a_k)(c_{ij}/a_i)=c_{ij}/\sum_k a_k=\pi_jq_{ji}\); for \(i=j\) the balance identity is automatic. Summing over \(i\) gives \(\sum_i\pi_iq_{ij}=0\), since the off-diagonal incoming terms equal \(\pi_j\sum_{i\ne j}q_{ji}\), which cancels \(\pi_jq_{jj}\). Thus \(\pi Q=0\), and for a finite generator the matrix exponential gives \(\pi e^{tQ}=\pi\): every positive power satisfies \(\pi Q^n=0\), so \(\pi e^{tQ}=\pi(I+\sum_{n\ge1}t^nQ^n/n!)=\pi\). The entries of \(\pi\) sum to one by their definition. \(\square\)

Common Pitfall: Confusing Conductances with Rates

A conductance is not always itself a transition rate. In the canonical walk it must be divided by the total conductance leaving its vertex. For example, on the triangle above, treating the conductances \(1,2,3\) as the off-diagonal rates gives a different generator: its rows are \((-3,1,2)\), \((1,-4,3)\), and \((2,3,-5)\), each of which sums to zero. Since this generator is symmetric, its stationary distribution is uniform, not \((1/4,1/3,5/12)\). A wrong calculation would use the canonical degree formula on these unnormalized rates: at state \(1\), the proposed degree-based balance has incoming flux \((1/3)(1)+(5/12)(2)=1/3+5/6=7/6\), while outgoing flux is \((1/4)(1+2)=3/4\). They are unequal.

The correction is to match the stationary calculation to the rates actually defined. For the canonical walk, divide each edge conductance by the degree at its source, giving the degree-proportional stationary distribution. If the raw conductances are used directly as rates, then the generator is symmetric and the uniform distribution balances each pair of rates. More generally, specify the holding-rate convention first, check that generator rows sum to zero, and then verify reversibility by computing \(\pi_iq_{ij}\) and \(\pi_jq_{ji}\) on every edge.