From Symmetric Flows to Transitions
A reversible chain can be designed by deciding how much probability mass should flow across each undirected edge. Symmetry of those flows is exactly the detailed-balance condition; dividing each flow by the mass assigned to its starting vertex gives a transition probability. The remaining mass at a vertex becomes a self-loop. The key constraint is that the total flow leaving a vertex cannot exceed its assigned mass.
Work on a finite state space \(S\). Let \((X_n)_{n\ge0}\) be a Markov chain on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). A transition matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\). We use unnormalized positive vertex weights \(m_i>0\), and write \(Z=\sum_{i\in S}m_i\) and \(\pi_i=m_i/Z\). Thus \(\pi\) is a probability distribution. For distinct states \(i,j\), let \(w_{ij}\ge0\) be the weight of the undirected edge between them, with \(w_{ij}=w_{ji}\). A zero weight means there is no edge.
If the edge weights already fit their budgets, meaning \(d_i\le m_i\) for every state, use the weights directly. More generally, choose a common scale \(\alpha>0\) such that \(\alpha d_i\le m_i\) for every \(i\). Define the off-diagonal flows \(c_{ij}=\alpha w_{ij}\), and put the unused budget at each vertex on its self-loop. This construction permits arbitrary finite edge weights and positive vertex weights: if some \(d_i>0\), any \(\alpha\) satisfying \(0<\alpha\le\min_{i:d_i>0}m_i/d_i\) works. If all \(d_i=0\), there are no off-diagonal edges and any positive \(\alpha\) works.
Why the Construction Works
Proof. Fix \(i\). Each off-diagonal entry is nonnegative, and \(p_{ii}=1-\alpha d_i/m_i\ge0\) by the budget condition. The row sum is
Thus \(P\) is row-stochastic. For \(i\ne j\), symmetry of the edge weights gives \(\pi_i p_{ij}=(m_i/Z)(\alpha w_{ij}/m_i)=\alpha w_{ij}/Z =\alpha w_{ji}/Z=\pi_jp_{ji}\). For \(i=j\), the detailed-balance identity has the same quantity on both sides. Finally, for each \(j\), summing detailed balance over \(i\) gives \(\sum_i\pi_i p_{ij}=\sum_i\pi_jp_{ji}=\pi_j\sum_i p_{ji}=\pi_j\); the last sum is row \(j\) of \(P\). Hence \(\pi P=\pi\), so \(\pi\) is stationary. \(\square\)
The theorem does not require the chain to be irreducible. If the graph has multiple connected components, the resulting chain may be reducible; the displayed \(\pi\) is still stationary, but it need not be the only stationary distribution. Nor does the construction guarantee a positive probability of staying put: \(p_{ii}=0\) when the whole budget \(m_i\) is used by outgoing edges.
Worked Example: A Weighted Path with Residual Self-Loops
Take \(S=\{1,2,3\}\), edge weights \(w_{12}=w_{21}=2\), \(w_{23}=w_{32}=1\), and \(w_{13}=w_{31}=0\). Let the vertex weights be \(m_1=3,m_2=4,m_3=2\), and use \(\alpha=1\). The degrees are \(d_1=2,d_2=3,d_3=1\), so \(2\le3\), \(3\le4\), and \(1\le2\): the budgets are sufficient.
Divide each off-diagonal flow by the starting vertex weight and use the residual budget for the diagonal. The resulting matrix is
Check the rows before using the matrix: row 1 sums to \(\tfrac13+\tfrac23+0=1\); row 2 sums to \(\tfrac12+\tfrac14+\tfrac14=1\); row 3 sums to \(0+\tfrac12+\tfrac12=1\). Here \(Z=3+4+2=9\), so \(\pi=(\tfrac13,\tfrac49,\tfrac29)\). Across edge \(1\leftrightarrow2\), the two flows are \(\pi_1p_{12}=\tfrac13\cdot\tfrac23=\tfrac29\) and \(\pi_2p_{21}=\tfrac49\cdot\tfrac12=\tfrac29\). Across edge \(2\leftrightarrow3\), they are \(\pi_2p_{23}=\tfrac49\cdot\tfrac14=\tfrac19\) and \(\pi_3p_{32}=\tfrac29\cdot\tfrac12=\tfrac19\). The absent edge has zero flow in both directions.
Check stationarity: the three coordinates of \(\pi P\) are \(\tfrac13\cdot\tfrac13+\tfrac49\cdot\tfrac12+\tfrac29\cdot0=\tfrac19+\tfrac29=\tfrac13\), \(\tfrac13\cdot\tfrac23+\tfrac49\cdot\tfrac14+\tfrac29\cdot\tfrac12=\tfrac29+\tfrac19+\tfrac19=\tfrac49\), and \(\tfrac13\cdot0+\tfrac49\cdot\tfrac14+\tfrac29\cdot\tfrac12=\tfrac19+\tfrac19=\tfrac29\). Thus \(\pi P=\pi\), as the theorem predicts.
Scaling When the Raw Weights Do Not Fit
When some weighted degree exceeds its vertex budget, the unscaled formula would give a negative self-loop probability. A common scale factor resolves this without changing which edges are present or the relative weights of those edges. For finite \(S\), the minimum of the finitely many positive ratios \(m_i/d_i\) exists whenever at least one degree is positive, so a positive admissible \(\alpha\) can always be chosen. Choosing the largest permissible common scale uses as much of at least one vertex budget as possible; choosing a smaller scale gives more residual self-loop probability.
Worked Example: Scaling a Triangle of Edge Weights
Let \(S=\{a,b,c\}\), with edge weights \(w_{ab}=w_{ba}=3\), \(w_{ac}=w_{ca}=2\), and \(w_{bc}=w_{cb}=1\). Let \(m_a=2,m_b=3,m_c=2\). The degrees are \(d_a=5,d_b=4,d_c=3\), so the three scale limits are \(m_a/d_a=2/5\), \(m_b/d_b=3/4\), and \(m_c/d_c=2/3\). Their minimum is \(2/5\); choose \(\alpha=2/5\).
The scaled edge flows are \(c_{ab}=6/5\), \(c_{ac}=4/5\), and \(c_{bc}=2/5\). Their totals at \(a,b,c\) are respectively \(2\), \(6/5+2/5=8/5\), and \(4/5+2/5=6/5\). The remaining budgets are \(0\), \(3-8/5=7/5\), and \(2-6/5=4/5\). Dividing each flow, including each residual loop flow, by its vertex weight gives
Each row sums to \(1\): row \(a\) is \(0+\tfrac35+\tfrac25=1\); row \(b\) is \(\tfrac25+\tfrac7{15}+\tfrac2{15}=\tfrac6{15}+\tfrac7{15}+\tfrac2{15}=1\); row \(c\) is \(\tfrac25+\tfrac15+\tfrac25=1\). The normalizing constant is \(Z=2+3+2=7\), so \(\pi=(\tfrac27,\tfrac37,\tfrac27)\). The edge-flow checks are \(\pi_ap_{ab}=\tfrac27\cdot\tfrac35=\tfrac6{35}=\tfrac37\cdot\tfrac25=\pi_bp_{ba}\); \(\pi_ap_{ac}=\tfrac27\cdot\tfrac25=\tfrac4{35}=\tfrac27\cdot\tfrac25=\pi_cp_{ca}\); and \(\pi_bp_{bc}=\tfrac37\cdot\tfrac2{15}=\tfrac2{35}=\tfrac27\cdot\tfrac15=\pi_cp_{cb}\). The diagonal balance identities hold automatically.
Check stationarity: the coordinates of \(\pi P\) are \(\tfrac27\cdot0+\tfrac37\cdot\tfrac25+\tfrac27\cdot\tfrac25=\tfrac6{35}+\tfrac4{35}=\tfrac27\), \(\tfrac27\cdot\tfrac35+\tfrac37\cdot\tfrac7{15}+\tfrac27\cdot\tfrac15=\tfrac6{35}+\tfrac{21}{105}+\tfrac2{35}=\tfrac{18}{105}+\tfrac{21}{105}+\tfrac6{105}=\tfrac37\), and \(\tfrac27\cdot\tfrac25+\tfrac37\cdot\tfrac2{15}+\tfrac27\cdot\tfrac25=\tfrac4{35}+\tfrac2{35}+\tfrac4{35}=\tfrac27\). Hence \(\pi P=\pi\).
Recovering the Flows from a Reversible Chain
Proof. In the first direction, nonnegativity follows from \(\pi_i>0\) and \(p_{ij}\ge0\), and detailed balance gives \(c_{ij}=\pi_i p_{ij}=\pi_jp_{ji}=c_{ji}\). The off-diagonal total is \(\sum_{j\ne i}c_{ij}=\pi_i\sum_{j\ne i}p_{ij}=\pi_i(1-p_{ii})\le\pi_i\), since \(p_{ii}\ge0\). In the converse direction, write the given positive masses as \(m_i\) and the symmetric flows as \(c_{ij}=c_{ji}\ge0\) for \(i\ne j\), with \(r_i=\sum_{j\ne i}c_{ij}\le m_i\). Set \(p_{ij}=c_{ij}/m_i\) for \(j\ne i\) and \(p_{ii}=(m_i-r_i)/m_i\). These entries are nonnegative and their row sum is \(r_i/m_i+(m_i-r_i)/m_i=1\). With \(Z=\sum_i m_i\) and \(\pi_i=m_i/Z\), for \(i\ne j\) we have \(\pi_i p_{ij}=c_{ij}/Z=c_{ji}/Z=\pi_jp_{ji}\); for \(i=j\) the identity is automatic. Thus the matrix is reversible with respect to \(\pi\). \(\square\)
This characterization explains the design principle in both directions: a reversible chain with positive stationary weights can be represented by symmetric flows, and symmetric flows within the vertex budgets define such a chain. The diagonal is not an extra edge constraint; it is precisely the leftover mass. If a vertex budget is exhausted, its self-loop is zero; if the vertex has no incident edges, its entire budget becomes a self-loop.
Worked Example: Why the Vertex Weights Matter
Take two states \(1,2\), one undirected edge with \(w_{12}=w_{21}=1\), and vertex weights \(m_1=1,m_2=2\). With \(\alpha=1\), the degrees are \(d_1=d_2=1\), which satisfy \(1\le1\) and \(1\le2\). The residual loop flows are \(0\) at state 1 and \(2-1=1\) at state 2. Dividing by the vertex weights gives \(P=\begin{bmatrix}0&1\\ \tfrac12&\tfrac12\end{bmatrix}\). Its rows sum to \(0+1=1\) and \(\tfrac12+\tfrac12=1\). The normalized vertex weights are \(\pi=(\tfrac13,\tfrac23)\). Detailed balance holds because \(\pi_1p_{12}=\tfrac13\cdot1=\tfrac13\) and \(\pi_2p_{21}=\tfrac23\cdot\tfrac12=\tfrac13\).
A common wrong calculation is to normalize each edge row by its own edge-weight total and set \(p_{12}=p_{21}=1\). That produces the deterministic alternating chain, whose stationary distribution is \((\tfrac12,\tfrac12)\), not the desired \((\tfrac13,\tfrac23)\). The edge weights alone do not impose the chosen vertex weights. The correction is to divide the symmetric flow by the mass of its starting vertex and assign the residual mass to the self-loop, as above.
Check Your Understanding
For each question, keep the vertex budgets distinct from the symmetric edge flows, and check every proposed transition row.
- For two states with \(m_1=2,m_2=3\) and a single edge flow of \(1\), compute the transition probabilities including both self-loops.
- For a finite weighted graph, explain why a positive common scale can be chosen when the vertex weights are all positive.
- If \(d_i=m_i/\alpha\) at a vertex, what is the self-loop probability there? Explain using the residual-budget formula.
- Show how the detailed-balance equation on an edge follows directly from symmetry of its flow.
- Can a reducible chain produced by this construction still have the stated stationary distribution? Explain why irreducibility is not used in the proof.