Reversible Random Walks on Weighted Graphs

From Edge Weights to Transition Probabilities

On an undirected graph, a walk can choose its next vertex in proportion to the weight of the edge leading there. This simple rule turns symmetric edge weights into transition probabilities. Symmetry then gives a direct balance relation: at stationarity, the probability flow across an edge is the same in both directions. The resulting stationary weights are determined by the total weight incident to each vertex.

Definition: Let $G=(V,E)$ be a finite undirected graph. Assign each unordered edge $\{i,j\}\in E$ a positive conductance $c_{ij}=c_{ji}>0$; put $c_{ij}=0$ when $\{i,j\}\notin E$, and set $c_{ii}=0$. The weighted degree of vertex $i$ is $c_i=\sum_{j\in V}c_{ij}$. In this tutorial, assume $c_i>0$ for every $i\in V$, so there are no isolated vertices. The conductance random walk has state space $S=V$ and transition probabilities $p_{ij}=c_{ij}/c_i$.

For a Markov chain $(X_n)_{n\ge0}$ on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with transition matrix $P=(p_{ij})$, a stationary distribution is a probability row vector $\pi$ satisfying $\pi P=\pi$. The chain need not start with distribution $\pi$ for this stationary distribution to exist. A distribution satisfying detailed balance, $\pi_i p_{ij}=\pi_j p_{ji}$ for all states $i,j$, is called reversible; detailed balance implies stationarity.

Theorem: For a finite undirected weighted graph with $c_i>0$ at every vertex, define $C=\sum_{i\in V}c_i$. The conductance walk is a valid transition matrix and has stationary distribution $$ \pi_i=\frac{c_i}{C},\qquad i\in V. $$ Moreover, it satisfies detailed balance. The conductance walk is irreducible if and only if the graph is connected.

Proof. For every $i$, $c_i>0$, and therefore $p_{ij}=c_{ij}/c_i$ is defined and nonnegative. Summing over $j$ gives $\sum_jp_{ij}=(\sum_jc_{ij})/c_i=1$, so each row of $P$ is a probability distribution. Also $C>0$, and $\sum_i c_i/C=1$, so $\pi$ is a probability distribution. For every pair $i,j$, $$ \pi_i p_{ij}=\frac{c_i}{C}\frac{c_{ij}}{c_i}=\frac{c_{ij}}{C} =\frac{c_{ji}}{C}=\frac{c_j}{C}\frac{c_{ji}}{c_j}=\pi_jp_{ji}. $$ Thus detailed balance holds. Summing this equality over $i$, with $j$ fixed, gives $\sum_i\pi_i p_{ij}=\pi_j\sum_i p_{ji}$ only if the indices are interpreted carefully; instead, use $\pi_i p_{ij}=c_{ij}/C$ and sum directly: $\sum_i\pi_i p_{ij}=\sum_i c_{ij}/C=c_j/C=\pi_j$. Hence $\pi P=\pi$. For irreducibility, recall that states communicate if each can be reached from the other in a finite number of transitions. If the graph is connected, any two vertices are joined by a finite edge path. Every edge on that path has positive conductance, so every corresponding transition probability is positive. The probability of following the whole path is the product of finitely many positive probabilities and is positive. Thus the chain is irreducible. Conversely, if the graph is disconnected, a path of transitions with positive probability cannot cross between distinct graph components: every transition between components has conductance zero and hence probability zero. States in different components do not communicate, so the chain is not irreducible. $\square$

The stationary distribution is therefore proportional to weighted degree, not generally uniform over vertices. A vertex incident to larger total conductance receives more stationary probability. Conductances determine the transition rule locally, while the normalization $C$ makes the degree weights sum to one globally.

Worked Example: A Weighted Path

Consider the path $1-2-3-4$, with conductances $c_{12}=2$, $c_{23}=1$, and $c_{34}=3$. Find its transition matrix and stationary distribution, and verify stationarity directly.

The weighted degrees are $c_1=2$, $c_2=2+1=3$, $c_3=1+3=4$, and $c_4=3$. Thus the transition matrix, with rows and columns ordered $1,2,3,4$, is

P= \begin{bmatrix} 0&1&0&0\\ \tfrac23&0&\tfrac13&0\\ 0&\tfrac14&0&\tfrac34\\ 0&0&1&0 \end{bmatrix}.

The row sums are $1$, $\tfrac23+\tfrac13=1$, $\tfrac14+\tfrac34=1$, and $1$. The total weighted degree is $C=2+3+4+3=12$. Hence the stationary distribution is

\pi=\left(\frac{2}{12},\frac{3}{12},\frac{4}{12},\frac{3}{12}\right) =\left(\frac16,\frac14,\frac13,\frac14\right).

To check $\pi P=\pi$, compute the probability entering each state: state $1$ receives $\tfrac14\cdot\tfrac23=\tfrac16$; state $2$ receives $\tfrac16\cdot1+\tfrac13\cdot\tfrac14=\tfrac16+\tfrac1{12}=\tfrac14$; state $3$ receives $\tfrac14\cdot\tfrac13+\tfrac14\cdot1=\tfrac1{12}+\tfrac14=\tfrac13$; state $4$ receives $\tfrac13\cdot\tfrac34=\tfrac14$. These are exactly the four entries of $\pi$, and they sum to $1$. As a separate balance check, the flow from $2$ to $3$ is $\tfrac14\cdot\tfrac13=\tfrac1{12}$, and the flow from $3$ to $2$ is $\tfrac13\cdot\tfrac14=\tfrac1{12}$.

Using the Distribution on a Small Graph

The formula gives the stationary distribution, but it does not by itself give the distribution at a particular time from an arbitrary initial state. If the initial distribution is the row vector $\mu_0$, then $\mu_1=\mu_0P$ and $\mu_2=\mu_1P$. These products use the transition matrix, not the stationary distribution formula in place of a time-step calculation.

Worked Example: A Weighted Triangle

Let the vertices be $A,B,C$, with conductances $c_{AB}=1$, $c_{AC}=2$, and $c_{BC}=3$. Find $P$, the stationary distribution, and the distributions after one and two steps when the chain starts at $A$.

The weighted degrees are $c_A=1+2=3$, $c_B=1+3=4$, and $c_C=2+3=5$. The transition matrix is

P= \begin{bmatrix} 0&\tfrac13&\tfrac23\\ \tfrac14&0&\tfrac34\\ \tfrac25&\tfrac35&0 \end{bmatrix}.

Its row sums are $\tfrac13+\tfrac23=1$, $\tfrac14+\tfrac34=1$, and $\tfrac25+\tfrac35=1$. The total degree is $C=3+4+5=12$, giving $\pi=(\tfrac14,\tfrac13,\tfrac5{12})$. Each stationary entry is a degree divided by $12$, and the entries sum to $\tfrac3{12}+\tfrac4{12}+\tfrac5{12}=1$.

Starting at $A$, $\mu_0=(1,0,0)$. Multiplying by $P$ selects its first row, so $\mu_1=(0,\tfrac13,\tfrac23)$. For the second step, weight the second row of $P$ by $\tfrac13$ and its third row by $\tfrac23$: the probability of $A$ is $\tfrac13\cdot\tfrac14+\tfrac23\cdot\tfrac25=\tfrac1{12}+\tfrac4{15}=\tfrac7{20}$; the probability of $B$ is $\tfrac13\cdot0+\tfrac23\cdot\tfrac35=\tfrac25$; and the probability of $C$ is $\tfrac13\cdot\tfrac34+\tfrac23\cdot0=\tfrac14$. Thus $\mu_2=(\tfrac7{20},\tfrac25,\tfrac14)$. Its entries sum to $\tfrac7{20}+\tfrac8{20}+\tfrac5{20}=1$. This distribution differs from $\pi$, as expected for a chain begun at a single vertex after only two steps.

Disconnected Graphs and Isolated Vertices

If the graph has multiple connected components but every vertex has positive weighted degree, the conductance walk remains defined on every vertex. No transition crosses between components. Each component therefore retains its total probability mass, and there can be multiple stationary distributions. For a component $V_r$, let $C_r=\sum_{i\in V_r}c_i$. If $\alpha_r\ge0$ are component masses with $\sum_r\alpha_r=1$, then assigning $\pi_i=\alpha_r c_i/C_r$ for $i\in V_r$ gives a stationary distribution. Indeed, within that component, the incoming mass at $j$ is $\sum_{i\in V_r}(\alpha_r c_i/C_r)(c_{ij}/c_i)=\alpha_r c_j/C_r$, and there is no incoming mass from other components.

Worked Example: Two Components with Different Masses

Take two disconnected edges, $\{1,2\}$ with conductance $2$ and $\{3,4\}$ with conductance $5$. All four weighted degrees are positive: $c_1=c_2=2$ and $c_3=c_4=5$. Each vertex moves to the other vertex in its own component, so

P= \begin{bmatrix} 0&1&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{bmatrix}.

Every row sums to $1$. Choose total stationary mass $\tfrac13$ on the first component and $\tfrac23$ on the second. Since each component has two vertices with equal degree, the distribution is $\pi=(\tfrac16,\tfrac16,\tfrac13,\tfrac13)$. Direct multiplication gives $\pi P=(\tfrac16,\tfrac16,\tfrac13,\tfrac13)=\pi$, and the entries sum to $1$. The global degree formula also produces a stationary distribution, namely $(\tfrac17,\tfrac17,\tfrac5{14},\tfrac5{14})$, because the total degree is $2+2+5+5=14$. The two distributions differ in their component masses, but both are stationary.

An isolated vertex is different: its weighted degree is zero, so the ratio $c_{ij}/c_i$ is undefined there. It is not correct to apply the conductance transition formula to that vertex or to include it in the normalization $C$ as though the formula defined a transition row. One may exclude isolated vertices from the state space, or separately specify transitions from them. The choice of those transitions is additional information, not determined by the edge conductances.

Worked Example: An Isolated Vertex Given a Separate Rule

Suppose vertices $1$ and $2$ form an edge of conductance $1$, while vertex $3$ is isolated. Define the chain on all three vertices by making $1$ and $2$ move to each other and by assigning a self-transition at $3$. The last rule is specified separately; it does not come from dividing by $c_3=0$. The transition matrix is

P= \begin{bmatrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{bmatrix}.

Each row sums to $1$. For any $a$ with $0\le a\le1$, let $\pi=(\tfrac a2,\tfrac a2,1-a)$. Multiplication gives $\pi P=(\tfrac a2,\tfrac a2,1-a)=\pi$, and the entries sum to $a+1-a=1$. Thus the isolated state can carry arbitrary stationary mass under this separately defined self-transition rule. This family is not obtained by applying the conductance formula at vertex $3$.

Reversibility, Connectivity, and a Common Error

For the conductance walk, the stationary probability flow along an edge has a particularly simple value: $$ \pi_i p_{ij}=\frac{c_{ij}}{C}. $$

This identity has two uses. It verifies reversibility edge by edge, and it shows why the stationary weight at a vertex is the sum of the conductances incident to it. It also highlights the role of symmetry: if the edge weights were directed rather than symmetric, the equality of forward and backward flows would not follow from this calculation.

A stationary distribution should not be confused with a limiting distribution. For example, on a single edge of conductance $1$, the transition matrix is $\begin{bmatrix}0&1\\1&0\end{bmatrix}$, and $(\tfrac12,\tfrac12)$ is stationary. Starting from vertex $1$, the distribution alternates between $(1,0)$ at even times and $(0,1)$ at odd times, so it does not converge to the stationary distribution. Stationarity is the equation $\pi P=\pi$; convergence from a specified initial law is a separate question.

Common mistake. On the weighted triangle above, one might guess that every vertex receives stationary probability $\tfrac13$ because the graph is undirected. But under the uniform row vector, the probability assigned to $A$ after one transition is $\tfrac13(0+\tfrac14+\tfrac25)=\tfrac{13}{60}$, which is not $\tfrac13$. The correction is to use weighted degrees: the stationary probability of $A$ is $3/12=\tfrac14$, not $\tfrac13$. A related error is to set $p_{ij}=c_{ij}/c_i$ at an isolated vertex; there $c_i=0$, so the formula has no value. Exclude that vertex or state its transition rule separately.

Check Your Understanding

For each question, check that any proposed transition row sums to $1$, and distinguish a stationary distribution from a time-$n$ distribution.

A path has edge conductances $1$ and $4$. Find the weighted degrees and the stationary distribution.
For an edge of conductance $3$ joining two vertices, write the conductance-walk transition matrix and its stationary distribution.
On a connected graph with positive conductances, why does every graph path give a positive-probability route for the chain?
Two nontrivial components have total degrees $6$ and $10$. Give a stationary distribution placing total mass $\tfrac14$ on the first component and $\tfrac34$ on the second, in terms of the degrees within each component.
Why is the conductance transition formula undefined at an isolated vertex, and what extra choice could make a Markov chain on the enlarged state space well-defined?