Stationary Measures for Random Walks on Graphs

Stationary Distributions and Detailed Balance

A random walk on a graph moves from its current vertex to a uniformly chosen neighbor. On a regular graph, every vertex has the same number of possible incoming and outgoing steps, so uniform probability is stationary. On an irregular graph, vertices with more incident edges receive more probability in the long-run balance: the stationary probability is proportional to degree. Detailed balance makes both claims precise by matching probability flow across each edge.

Throughout, graphs are finite and simple. Unless stated otherwise, assume the graph has no isolated vertices, so the walk is defined at every vertex. From a vertex $u$, the simple random walk moves to each neighbor with probability $1/\deg(u)$. Write $P(u,v)$ for the probability of moving from $u$ to $v$ in one step. Thus $P(u,v)=1/\deg(u)$ when $uv\in E$, and $P(u,v)=0$ otherwise. A probability distribution $\pi$ assigns nonnegative numbers $\pi(v)$ to vertices, with $\sum_{v\in V}\pi(v)=1$.

Definition: A probability distribution $\pi$ is stationary for the walk if, when the current vertex has distribution $\pi$, the vertex after one step also has distribution $\pi$. In equations, this means $$ \pi(v)=\sum_{u\in V}\pi(u)P(u,v)\qquad\text{for every }v\in V. $$

The term $\pi(u)P(u,v)$ is the probability mass that moves from $u$ to $v$ in one step when the current distribution is $\pi$. A useful stronger condition is to balance that flow separately across every pair of vertices.

Definition: A distribution $\pi$ satisfies detailed balance if $\pi(u)P(u,v)=\pi(v)P(v,u)$ for all vertices $u,v$. In particular, this requires equal flow in the two directions along each edge.

Detailed balance is sufficient for stationarity. Indeed, summing its equality over all possible starting vertices $u$ gives the stationarity equation at $v$: the total mass arriving at $v$ equals $\sum_u \pi(v)P(v,u)=\pi(v)$, since the probabilities of moving from $v$ to its possible destinations sum to $1$. We will use this implication to derive the graph formulas.

The Degree-Proportional Distribution

Theorem: Let $G=(V,E)$ be a finite undirected graph with no isolated vertices and at least one edge. For its simple random walk, the distribution $$ \pi(v)=\frac{\deg(v)}{\sum_{w\in V}\deg(w)}=\frac{\deg(v)}{2|E|} $$ is stationary and satisfies detailed balance.

Proof. Let $m=|E|$. Each edge has two endpoints and contributes one to the degree of each endpoint, so summing degrees counts every edge twice: $\sum_w\deg(w)=2m$. Since the graph has at least one edge and no isolated vertices, every degree is positive and $2m>0$. Thus the displayed values are positive and sum to $1$. If $uv$ is an edge, then $\pi(u)P(u,v)=(\deg(u)/(2m))(1/\deg(u))=1/(2m)$, and likewise $\pi(v)P(v,u)=1/(2m)$. If $uv$ is not an edge, both transition probabilities are zero, so the two flows are both zero. Therefore detailed balance holds for every pair $u,v$; as shown above, it implies stationarity. $\square$

The formula assigns equal stationary flow to every directed traversal of an edge: under $\pi$, the flow in either direction along any particular edge is $1/(2m)$. A vertex of degree $d$ has $d$ incident edges and therefore receives total incoming flow $d/(2m)$, exactly its assigned mass.

Worked Example: The Uniform Distribution on a Regular Graph

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34,41\}$, the cycle $C_4$. Each vertex has degree $2$, so the graph is $2$-regular. There are four vertices, and the uniform distribution assigns $\pi(v)=1/4$ to each one.

For any edge $uv$, the probability of moving from $u$ to $v$ is $1/2$. The flow in either direction is therefore $\pi(u)P(u,v)=(1/4)(1/2)=1/8$, and $\pi(v)P(v,u)=(1/4)(1/2)=1/8$. For a direct stationarity check at vertex $1$, its neighbors are $2$ and $4$, so its incoming mass is $(1/4)(1/2)+(1/4)(1/2)=1/8+1/8=1/4$. The same calculation applies at each vertex, since each has two neighbors. The probabilities sum to $4(1/4)=1$, so the uniform distribution is stationary.

Check: the degree formula gives $\pi(v)=2/(2\cdot4)=2/8=1/4$ for every vertex, agreeing with the direct calculation.

Regular Graphs and the Uniform Distribution

Corollary: On any finite $d$-regular graph with $d\geq1$, the uniform distribution $\pi(v)=1/|V|$ is stationary and satisfies detailed balance.

Proof. In a $d$-regular graph each degree equals $d$, so the degree-proportional distribution has value $d/\sum_w d=d/(|V|d)=1/|V|$ at every vertex. The theorem therefore gives the stated distribution and detailed balance. Equivalently, on each edge both directed flows are $(1/|V|)(1/d)$; at a vertex, the $d$ incoming contributions sum to $d(1/(|V|d))=1/|V|$. $\square$

This conclusion includes a connected or disconnected regular graph, provided $d\geq1$. Regularity makes the degree-proportional distribution uniform, but the same degree formula continues to work when degrees differ.

Worked Example: The Degree Distribution on a Path

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$, the path $P_4$. Its degrees are $\deg(1)=1$, $\deg(2)=2$, $\deg(3)=2$, and $\deg(4)=1$. Their sum is $1+2+2+1=6$, so the proposed distribution is $\pi=(1/6,2/6,2/6,1/6)$, in vertex order $1,2,3,4$. The entries sum to $6/6=1$.

Check each vertex using the incoming-flow equation. Vertex $1$ receives all its incoming mass from $2$, which moves to $1$ with probability $1/2$; its incoming mass is $(2/6)(1/2)=1/6$. Vertex $2$ receives mass from $1$ with probability $1$, and from $3$ with probability $1/2$, giving $(1/6)(1)+(2/6)(1/2)=1/6+1/6=2/6$. Vertex $3$ receives $(2/6)(1/2)$ from $2$ and $(1/6)(1)$ from $4$, totaling $1/6+1/6=2/6$. Vertex $4$ receives $(2/6)(1/2)=1/6$ from $3$. Each incoming total equals the proposed mass at that vertex.

Check: on each edge, the flow in either direction is $1/6$. For example, along $23$ the flow from $2$ to $3$ is $(2/6)(1/2)=1/6$, and from $3$ to $2$ it is also $(2/6)(1/2)=1/6$. This independently checks detailed balance on all three edges, whose endpoints have the same degree pairs as the two internal vertices and the two end vertices.

Connectedness, Disconnectedness, and Uniqueness

The formula $\deg(v)/(2m)$ gives a stationary distribution even when the graph is disconnected, as long as it has no isolated vertices. But disconnectedness affects uniqueness: the walk cannot move between connected components, so a stationary distribution can place different total probability on different components. Here a connected component is a maximal set of vertices in which every pair can be joined by a path.

Theorem: If $G$ is connected, finite, undirected, and has at least one edge, the degree-proportional stationary distribution is the only stationary distribution. If $G$ has several connected components and no isolated vertices, any stationary distribution is a mixture of the degree-proportional distributions on those components.

Proof. First consider a connected graph and let $\pi$ be its degree-proportional distribution. It is positive at every vertex and satisfies detailed balance. Let $\mu$ be any stationary distribution, and define $a(v)=\mu(v)/\pi(v)$. Since $\pi(v)>0$, this ratio is defined. Stationarity of $\mu$, followed by detailed balance for $\pi$, gives $$ a(v)=\frac{\sum_u\mu(u)P(u,v)}{\pi(v)} =\sum_u\frac{\pi(u)P(u,v)}{\pi(v)}a(u) =\sum_u P(v,u)a(u). $$ The last equality uses $\pi(u)P(u,v)=\pi(v)P(v,u)$. Thus $a(v)$ is a weighted average of the values $a(u)$ at neighbors of $v$, with nonnegative weights $P(v,u)$ summing to $1$. Since there are finitely many vertices, $a$ attains a maximum $M$. At a vertex $v$ attaining $M$, its weighted average equals $M$. Every neighbor has value at most $M$, and every neighbor receives positive weight $1/\deg(v)$; therefore every neighbor must also have value $M$. Repeating this argument along paths and using connectedness shows $a(u)=M$ for every vertex $u$. Hence $\mu=M\pi$; since both distributions sum to $1$, $M=1$, so $\mu=\pi$.

For a graph with components $C_1,\dots,C_k$, no transition crosses between components. The restriction of a stationary distribution to a component, if it has positive total mass, must after normalization be stationary for the walk on that component; the connected case just proved forces it to be that component's degree-proportional distribution. A component assigned zero mass contributes zero at each of its vertices. Thus the global stationary distributions are exactly mixtures of the component distributions, with nonnegative mixture weights summing to $1$. $\square$

Worked Example: A Disconnected Graph Has Many Stationary Distributions

Let $G$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,31,45\}$. Its components are a triangle on $\{1,2,3\}$ and an edge on $\{4,5\}$. The degrees are $2,2,2,1,1$, with sum $2+2+2+1+1=8$. The global degree-proportional distribution is $\pi(1)=\pi(2)=\pi(3)=2/8=1/4$ and $\pi(4)=\pi(5)=1/8$. The total mass is $3(1/4)+2(1/8)=3/4+1/4=1$.

Each triangle vertex receives mass from its two triangle neighbors, each of which moves to it with probability $1/2$. For vertex $1$, for example, the incoming mass is $(1/4)(1/2)+(1/4)(1/2)=1/8+1/8=1/4$. Vertices $2$ and $3$ have the same two-neighbor calculation. Vertices $4$ and $5$ move to each other with probability $1$, so each receives $1/8$, equal to its assigned mass. Thus the distribution is stationary. Its mass on the triangle is $3/4$, and on the single edge it is $1/4$.

There are other stationary distributions. For instance, assign probability $1/3$ to each of $1,2,3$ and probability $0$ to $4,5$. Each triangle vertex receives $2((1/3)(1/2))=1/3$, and the edge component remains at zero, so this is stationary too. The walk stays within whichever component it starts in; therefore the relative mass assigned to the components is not determined by stationarity.

Check: the degree-proportional distribution has edge flow $(1/4)(1/2)=1/8$ in either direction along each triangle edge, and $(1/8)(1)=1/8$ in either direction along edge $45$. These values agree with the general flow $1/(2m)=1/8$, since this graph has $m=4$ edges.

Common Pitfall: Assuming Uniformity on an Irregular Graph

The uniform distribution is not generally stationary on an irregular graph. The $P_4$ example shows the error directly. If each of its four vertices is assigned mass $1/4$, then the incoming mass at vertex $1$ is only $(1/4)(1/2)=1/8$, because its sole neighbor $2$ chooses $1$ with probability $1/2$. This is not the proposed mass $1/4$. At vertex $2$, the incoming mass would be $(1/4)(1)+(1/4)(1/2)=1/4+1/8=3/8$, also not $1/4$. The discrepancy arises because the endpoint and internal vertices have different degrees. Replacing uniform mass with the degree-proportional values $(1/6,2/6,2/6,1/6)$ makes every directed edge flow equal and restores stationarity.

There is a second assumption to watch: an isolated vertex has no neighbor, so the rule “choose a neighbor uniformly” does not define a transition from it. The degree formula above was stated for graphs without isolated vertices. One can define a different walk that stays at isolated vertices, but that is an additional convention and must be handled separately. Likewise, a graph consisting only of isolated vertices has $\sum_v\deg(v)=0$, so the degree-proportional formula cannot be normalized.

Check Your Understanding

Use the incoming-flow equation and detailed balance to justify your answers.

For a $3$-regular graph on $10$ vertices, what is the stationary mass at each vertex, and what is the flow in either direction along one edge?
For the graph with $V=\{a,b,c\}$ and $E=\{ab,bc\}$, compute the degree-proportional stationary distribution and verify the incoming mass at $b$.
Explain why equal flow in both directions along every edge implies the stationarity equation at each vertex.
Why does a connected graph with no isolated vertices have a unique stationary distribution, while a disconnected graph can have more than one?
What is undefined about the simple random walk at an isolated vertex, and why does the degree formula not resolve that problem?