First realize the chain as a random walk on a multigraph: put three parallel edges between , two between , and one between . There are six edges and vertex degrees . Choosing an incident edge uniformly gives exactly the stated transition probabilities. The stationary distribution of a graph random walk is the degree divided by twelve, , and detailed balance follows because each edge multiplicity contributes the same flux in both directions.
For the first positive return time, Kac's lemma gives
For passage to , put and . The first-step equations are and , since reaching stops the clock. Thus
A multigraph is essential: a simple graph on three vertices cannot have six edges.
For the usual undirected graph with at least two vertices, a simple random walk chooses a neighbor uniformly at each step, so when and are adjacent and zero otherwise, where is the degree of a vertex. The handshaking lemma gives . Thus the stationary distribution of a graph random walk is
For adjacent , , and for nonadjacent pairs both sides vanish. By detailed balance, this is an invariant distribution and the walk started from it is a reversible Markov chain. Connectedness makes the finite walk an irreducible Markov chain, giving uniqueness of its invariant distribution. No aperiodicity assumption is needed for uniqueness, so a bipartite graph is allowed.
If the connected graph has a single isolated vertex, the usual neighbor-choice formula is undefined. With the natural absorbing convention , its unique invariant distribution is and it is reversible. The degree-normalization formula presupposes at least one edge.
Stationary distribution of a graph random walk Created 2026-09-24 Updated 2026-11-05
On a finite connected loopless undirected graph with at least two graph vertices, the stationary distribution of a graph random walk for the simple random walk is
More generally, for positive symmetric edge electrical conductances with no killing, replace the vertex degree by and by . The detailed balance identity proves stationarity directly.
The stationary distribution is uniform precisely when the connected unweighted graph is regular. For a star with leaves, the center has stationary mass and each leaf has stationary mass . Starting at the center, the probability distribution alternates between center and leaves, so it does not converge to stationarity without an aperiodicity mechanism such as a positive holding probability. For a disconnected graph, different closed components admit different stationary mixtures; isolated graph vertices require an explicit transition convention.