Motivation
A stationary distribution is unchanged by one step of a Markov chain. Its existence is not the same as convergence to it: a chain can have a stationary distribution while oscillating forever from a particular starting state. Laziness, which allows the chain to stay in place, can remove that oscillation.
We first prove that every finite chain has a stationary distribution. Then we give a quantitative convergence proof under explicit irreducibility and self-loop assumptions. As an application, a lazy random walk on a connected undirected graph converges to a degree-weighted distribution.
Definitions
Definition 5.4.1
(Stationary distribution and irreducibility)
Let be a transition matrix on a finite nonempty state space . A row probability vector is stationary if . The chain is irreducible if every state can reach every other state along a finite path of positive-probability transitions.
Definition 5.4.2
(Total variation distance)
Total variation distance is . We use the coupling inequality proved in the companion chapter: for any coupling of distributions , their total variation distance is at most the probability that the coupled states differ.
Theorems
Theorem 5.4.3
(A finite stationary distribution exists)
Every finite Markov chain has at least one stationary probability distribution.
Theorem 5.4.4
(Convergence with an accessible self-loop)
Suppose a finite chain is irreducible and has a state with . Then it has a unique stationary distribution , and there exist an integer and such that, for every initial distribution and integer ,
Proof: Cesàro averages
Proof
(Cesàro averages have a stationary limit point)
Choose any initial distribution and define
The probability simplex is compact, so the sequence has a convergent subsequence. Its difference after one transition telescopes:
Every coordinate of the numerator is bounded, so the difference tends to zero. If along a subsequence, continuity of matrix multiplication gives . The limit remains a probability vector. This proves existence without assuming irreducibility or convergence of the original sequence .
Proof X-ray
Compactness and telescoping replace convergence
Compactness supplies a limit point and telescoping shows that it is stationary; neither irreducibility nor convergence of is used. The boundary term has every coordinate of absolute value at most , because and are probability vectors, so it tends to zero even when individual distributions oscillate. Passing to the limit along the subsequence uses continuity of right multiplication by , which holds because the state space is finite, and the limit is a probability vector because the simplex is closed. On the alternating two-state chain the distributions swap forever, yet the averages converge to .
Proof: a common destination
Proof
(Coupling through a common destination)
By irreducibility, every state has a positive-probability path to . Choose one finite path for each . Let be at least the length of every chosen path. Pad a shorter path with self-loops at until it has exactly steps. Its probability is positive, so for every .
There are finitely many states, so . Also . For each , decompose the -step transition distribution into a common mass at and a residual probability distribution. If , every state reaches with probability one in steps and the next argument is immediate. Otherwise, the residual distribution is
To couple two copies over a block of steps, use a common Bernoulli decision with probability . On success put both block endpoints at ; otherwise sample their endpoints from their respective residual distributions. Each endpoint has its correct marginal. Once the copies coincide, use the same future transitions for both so that they remain equal.
Conditional on not having met before a block, the chance of meeting at its end is at least . Thus the chance they remain different after blocks is at most . Couple a chain started from with one started from a stationary distribution . The second marginal stays at block times, and the coupling inequality gives the displayed bound.
If is another stationary distribution, start the first copy from . Then for every , so the distance is zero and . This proves uniqueness.
Proof X-ray
One shared coin for every starting state
The non-routine idea is the decomposition with the same for every . It lets two copies started at different states use a single shared coin, so both sit at with probability at least whatever their positions. The self-loop at is used only to pad every path to a common length . Without a common length, can be zero, as for a periodic chain.
Irreducibility supplies a path from every state, and finiteness makes the minimum positive. The argument closes geometrically: each block is a fresh chance, conditional on not having met, so the failure probabilities multiply to . The coupling only constrains block endpoints, which is all the coupling inequality needs.
Lazy random walk on an undirected graph
Let be a finite connected loopless undirected multigraph with at least two vertices and edge copies. At vertex , stay at with probability ; otherwise choose an incident edge copy uniformly and traverse it. Every degree is positive. Define
Proposition 5.4.5
(Stationary distribution of the lazy walk)
The lazy random walk above has a unique stationary distribution, namely , and the convergence theorem applies to it.
Proof
(Detailed balance for the lazy walk)
The degree sum is , so is a probability distribution. For distinct adjacent vertices with parallel edge copies,
The same detailed-balance identity is trivial for and both sides are zero for nonadjacent vertices. Summing over gives stationarity. Connectedness gives irreducibility, and every vertex has a self-loop probability , so the convergence theorem applies. The stationary distribution is uniform only when all degrees are equal.
Worked examples
Worked example 5.4.6
(A two-state oscillation)
A nonlazy walk on one edge alternates deterministically between its two endpoints. The uniform distribution is stationary, but a walk started at one endpoint alternates between two point masses and never converges to uniform. A self-loop is absent, so the convergence theorem above does not apply.
Worked example 5.4.7
(A lazy two-state walk)
On the same edge, the lazy walk stays or crosses with probability one half each. After one step its distribution is uniform regardless of its starting endpoint. The theorem's assumptions hold.
Worked example 5.4.8
(A path on three vertices)
For the path , the degrees are one, two and one. Its lazy walk has stationary probabilities , , . The middle vertex is visited twice as often in stationarity as either endpoint.
Worked example 5.4.9
(A reducible chain)
If both states of a two-state chain are absorbing, every distribution on them is stationary. Existence holds, but uniqueness fails because the chain is not irreducible.
Common mistakes
Counterexample mode
Stationary does not mean every start is stationary
The alternating two-state chain has uniform stationary distribution, but a point mass remains a point mass at each time and alternates endpoints. A stationary distribution describes what happens when the chain starts in that distribution; convergence from other starts requires additional conditions.
Common mistake
(A self-loop is sufficient, not necessary)
The proof assumes an accessible self-loop at some state, a sufficient condition stronger than the most general aperiodicity criterion. It does not claim that every aperiodic irreducible finite chain has a self-loop, even though a broader convergence theorem exists.
Common mistake
(Coupling controls block endpoints only)
The common-destination coupling controls block endpoints. It does not say the original chains must follow identical intermediate paths during a block. A full within-block coupling can be obtained by sampling paths conditional on the chosen endpoints, but the total-variation bound only uses the block endpoint distributions.
From block times to every time
The theorem states a bound at multiples of . It also implies convergence at intermediate times. Applying the same transition matrix to two distributions cannot increase total variation distance. To see this by coupling, start with a maximal coupling of the two distributions; when its states are equal, use the same next state for both, sampled from the appropriate transition row. When they differ, use any coupling of the two rows. The probability of disagreement after the step is no larger than before it.
Write with . Since , applying to both distributions gives
The bound may be conservative: the paths chosen to define can have very small probabilities. Its purpose is to prove convergence from every initial distribution under the stated hypotheses. A sharp mixing-time estimate generally needs more information about the chain.
Aperiodicity without a self-loop
The self-loop hypothesis is convenient but not necessary for a finite irreducible chain to be aperiodic. Consider states with transitions and of probability one, and transitions and each of probability one half. There are no self-loops, and every state can reach every other state.
State zero has positive-probability returns of lengths two and three: and . Their greatest common divisor is one. State one also has returns of lengths two and three, and state two has returns of lengths three and five. Thus every state has period one under the usual definition as the greatest common divisor of positive return times. The chain is aperiodic despite having no one-step self-loop.
Our proof does not use the general aperiodic theorem; it uses a self-loop to pad selected paths to one common length. A broader proof can replace this convenient hypothesis by a general aperiodicity argument, but that is not established here.
Detailed balance and stationarity
The lazy-walk calculation uses detailed balance: for every pair of states. Summing over gives
because the row of from sums to one. Thus detailed balance is a sufficient condition for stationarity. It is not part of the definition of stationarity, and some stationary chains are not reversible.
For example, the deterministic directed cycle has a uniform stationary distribution, but positive flow from zero to one and no one-step flow from one to zero. It does not satisfy detailed balance with the uniform distribution. This example separates invariance of a distribution from the stronger pairwise flow symmetry.
What the degree weights mean
In an undirected graph, each edge contributes one incident half-edge at each endpoint. A simple random walk chooses among incident edge copies, so vertices of larger degree receive proportionally more stationary mass. The factor from laziness cancels in the detailed-balance calculation for transitions between distinct vertices; it changes the speed of the walk but not this stationary distribution.
For a star with one center and leaves, the center has degree and each leaf has degree one. There are edges, so the center has stationary probability and each leaf has probability . The probabilities sum to one. Treating all vertices as equally likely would be correct only when their degrees are equal.
The theorem assumes a connected loopless graph with at least two vertices so every degree is positive and the edge-selection rule is defined. A one-vertex graph can be treated separately by declaring its only state absorbing; its stationary distribution is the point mass there. A disconnected graph has separate communicating components and may have multiple stationary distributions.
The simple walk on the integers has no stationary probability distribution, because compactness is lost.
A path to generalization
What fails on an infinite state space?
The simple walk on the integers has no stationary probability distribution, because compactness is lost.
Existence used finiteness through compactness of the simplex. On , the walk that moves one step left or right with probability would need for every . Then is linear; nonnegativity forces , and summing to one forces , a contradiction. Every Cesàro average of the walk still exists, but it spreads out and its limit points are not probability distributions. Infinite chains therefore need extra hypotheses for a stationary distribution to exist.
For and target , it is sufficient to take blocks, rounded up. If , one block suffices. This gives an explicit, though potentially loose, mixing-time upper bound once the chosen path probabilities are known.
The parameter is the maximum length of the selected paths to , enlarged to at least one. It need not be the smallest possible common length. The parameter is the minimum of the actual -step probabilities of reaching ; the probabilities of the selected padded paths give a computable positive lower bound on it. Different choices of and paths can change the resulting numerical estimate without affecting the validity of the convergence proof. In a concrete application, comparing several such choices can improve the bound, although it need not make the final bound sharp for a particular chain.
Summary
Cesàro averages give a stationary distribution for every finite chain. Irreducibility plus one positive self-loop gives a common destination after a fixed number of steps, yielding a geometric coupling bound and uniqueness. A connected lazy undirected walk has stationary probabilities proportional to degree.
Exercises
Quick check
(Why does the alternating two-state chain have a uniform stationary distribution?)
Swap the two equal probabilities and compare.
Solution · Answer
Swapping the two equal probabilities leaves the uniform vector unchanged.
Quick check
(What is the stationary distribution of a lazy walk on a three-vertex path?)
Compute the degrees along the path.
Solution · Answer
It is in path order, because the degrees are one, two and one.
Quick check
(Why is the common mass strictly positive?)
It is a minimum over finitely many positive numbers.
Solution · Answer
Each of finitely many states has a positive-probability path of the same padded length to . The minimum of finitely many positive numbers is positive.
Quick check
(Why does the existence proof use a convergent subsequence of averages rather than assert that converges?)
Think of the alternating chain.
Solution · Answer
Individual distributions can oscillate, as the alternating chain shows. Compactness guarantees a convergent subsequence of averages, whose telescoping limit is stationary.