Stationary Distributions for Random Walks on Graphs

Why Vertex Degree Determines Stationary Mass

A random walk on an undirected graph chooses one of the current vertex’s neighbors uniformly at each step. A vertex with many neighbors sends probability away along many possible edges, but it can also be entered from many neighboring vertices. At equilibrium, these two effects balance: the stationary probability at a vertex is proportional to its number of neighbors. We will derive that distribution and verify the balance on every edge.

Let \(G=(V,E)\) be a finite, connected, undirected simple graph with at least two vertices. “Simple” means there are no loops or multiple edges. Write \(i\sim j\) when \(\{i,j\}\in E\), and let \(d(i)\) be the number of neighbors of \(i\). Connectedness and the assumption \(|V|\ge2\) imply \(d(i)\ge1\) for every vertex. On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((X_n)_{n\ge0}\) be the discrete-time Markov chain with state space \(V\), transition matrix \(P=(p_{ij})\), and initial distribution \(\mu\), a row vector. Its transition probabilities are

For each \(i\), there are exactly \(d(i)\) neighbors, each assigned probability \(1/d(i)\), and every other transition has probability zero. Thus \(\sum_{j\in V}p_{ij}=d(i)/d(i)=1\): \(P\) is row-stochastic. A probability row vector \(\pi\) is stationary if \(\pi P=\pi\); starting the chain with distribution \(\pi\) then leaves its one-time marginal distribution unchanged at each step.

Derivation by Balancing Each Edge

Detailed balance asks that, for each ordered pair \(i,j\), the stationary probability flow from \(i\) to \(j\) equal the flow from \(j\) to \(i\). For an undirected graph, a natural candidate assigns the same stationary flow to each direction of every edge. If \(i\sim j\), the transition probability out of \(i\) along that edge is \(1/d(i)\). Choosing \(\pi_i\) proportional to \(d(i)\) makes the product \(\pi_i p_{ij}\) independent of the vertex degree.

The denominator \(2|E|\) follows by counting vertex-edge incidences. Each edge has two endpoints, so counting incidences by edges gives \(2|E|\); counting them by vertices gives \(\sum_{i\in V}d(i)\). Consequently, \(\sum_i d(i)=2|E|\), and the proposed probabilities sum to one.

Proof. Set \(D=\sum_{k\in V}d(k)=2|E|\), and define \(\pi_i=d(i)/D\). Since every degree is positive and the sum of the degrees is \(D\), each \(\pi_i\) is nonnegative and \(\sum_i\pi_i=1\). If \(i\sim j\), then \(\pi_i p_{ij}=(d(i)/D)(1/d(i))=1/D\), and, because the graph is undirected, \(\pi_j p_{ji}=(d(j)/D)(1/d(j))=1/D\). If \(i\not\sim j\), then \(p_{ij}=p_{ji}=0\), so both flows are zero. Thus detailed balance holds for all pairs. For a fixed \(j\), it follows that \(\sum_i\pi_i p_{ij}=\sum_i\pi_j p_{ji}=\pi_j\sum_i p_{ji}\). Here \(p_{ji}\), as \(i\) ranges over \(V\), is row \(j\) of \(P\), so its sum is \(1\). Hence \(\sum_i\pi_i p_{ij}=\pi_j\), proving \(\pi P=\pi\). \(\square\)

There is also a direct reason the candidate works: every neighbor of \(j\) sends the same stationary flow \(1/D\) into \(j\), and there are \(d(j)\) such neighbors. The total incoming flow is therefore \(d(j)/D=\pi_j\). The proof above establishes the same fact while also checking detailed balance for nonedges.

Uniqueness. Connectedness rules out separate components that could carry different stationary distributions. The following argument proves uniqueness directly, without needing a convergence claim.

Proof. Let \(\nu\) be any stationary probability distribution for this chain, so \(\nu P=\nu\), and define \(r_i=\nu_i/\pi_i\); this ratio is defined because \(\pi_i>0\). For each \(j\), stationarity and detailed balance give \(\displaystyle r_j=\frac{\nu_j}{\pi_j}=\sum_i\frac{\nu_i p_{ij}}{\pi_j}=\sum_i r_i\frac{\pi_i p_{ij}}{\pi_j}=\sum_i r_i p_{ji}\). The last expression is a weighted average of the values \(r_i\) at the neighbors of \(j\): its weights are \(p_{ji}=1/d(j)\) for those neighbors and zero otherwise. Since \(V\) is finite, \(r\) has a maximum, say at \(j\). Its average over the neighbors of \(j\) equals this maximum. Each neighbor’s value is at most the maximum, so every neighbor must also have the maximum value; otherwise the average would be smaller. Repeating this argument along paths, connectedness implies that every \(r_i\) equals the same constant \(c\). Thus \(\nu_i=c\pi_i\) for every \(i\). Summing over \(i\) gives \(1=c\cdot1\), so \(c=1\) and \(\nu=\pi\). \(\square\)

Worked Examples

Stationary Does Not Mean Convergent

The degree formula identifies a stationary distribution, not necessarily the limiting distribution of the chain from every initial state. For instance, take the connected graph consisting of one edge between vertices \(1\) and \(2\). Its transition matrix is \(\begin{bmatrix}0&1\\1&0\end{bmatrix}\), and its stationary distribution is \((\tfrac12,\tfrac12)\). Starting at vertex \(1\), the distribution at even times is \((1,0)\) and at odd times is \((0,1)\), so it does not converge. This example is enough to show why stationarity and convergence must not be treated as synonyms; no claim about a limiting distribution is needed for the degree-proportional result.

Common mistake: using a uniform distribution on an irregular graph. On the four-vertex path above, the uniform row vector would be \(\eta=(\tfrac14,\tfrac14,\tfrac14,\tfrac14)\). Its first coordinate after one step is \((\eta P)_1=\eta_2p_{21}=\tfrac14\cdot\tfrac12=\tfrac18\), which is not \(\eta_1=\tfrac14\). Thus \(\eta\) is not stationary. The correction is to weight each vertex by its degree: the path’s stationary mass at an interior vertex is twice its mass at an endpoint, yielding \((\tfrac16,\tfrac13,\tfrac13,\tfrac16)\). On a regular graph, by contrast, all degrees are equal, so the degree-proportional distribution is uniform.

For a finite connected undirected graph with at least two vertices, the calculation can be applied in three checks: confirm the graph’s degrees, normalize those degrees by their sum, then verify that each edge carries equal flow in both directions. The theorem guarantees that this distribution is stationary and unique. If the graph is not connected, the connectedness argument for uniqueness no longer applies: separate components do not exchange probability mass.