5.4 Stationary distributions

Definition of stationary distributions

A stationary distribution is a probability distribution over the states of a Markov chain that remains unchanged when you apply the transition matrix. Think of it as the equilibrium of the system: once the chain settles into this distribution, it stays there forever.

Formally, a stationary distribution is a row vector $\pi = (\pi_1, \pi_2, \dots, \pi_n)$ satisfying two conditions:

• $\pi P = \pi$, where $P$ is the transition probability matrix
• $\sum_i \pi_i = 1$ and $\pi_i \geq 0$ for all $i$

The entries of $\pi$ tell you the long-run proportion of time the chain spends in each state. If a chain has states $\{1, 2, 3\}$ and $\pi = (0.2, 0.5, 0.3)$, then in the long run the chain spends 50% of its time in state 2.

Properties of stationary distributions

Invariance under state transitions

The defining property of a stationary distribution is that it's a fixed point of the transition dynamics. If the chain's state distribution at time $t$ is $\pi$, then at time $t+1$ it's $\pi P = \pi$, and by induction:

$\pi P^n = \pi \quad \text{for all } n \geq 0$

This means that if you start the chain with initial distribution $\pi$, the marginal distribution at every future time step is still $\pi$. The chain looks statistically identical at every point in time.

Uniqueness of stationary distributions

A stationary distribution is not always unique. A reducible chain (one with multiple closed communicating classes) can have infinitely many stationary distributions, since you can form convex combinations of the stationary distributions within each closed class.

Uniqueness is guaranteed when the chain is irreducible (all states communicate). In that case, if a stationary distribution exists, there is exactly one. This is a direct consequence of the Perron-Frobenius theorem applied to stochastic matrices. The practical upshot: for an irreducible chain, the long-run behavior doesn't depend on where you started.

Existence of stationary distributions

Three concepts control whether a stationary distribution exists: irreducibility, aperiodicity, and positive recurrence. They play different roles, so it's worth being precise about which condition does what.

Irreducible Markov chains

A Markov chain is irreducible if every state can be reached from every other state in some finite number of steps. Formally, for all states $i, j$, there exists $n > 0$ such that $P^n(i,j) > 0$.

Irreducibility alone does not guarantee a stationary distribution exists. Consider a symmetric random walk on $\mathbb{Z}$: it's irreducible, but no stationary distribution exists because the state space is infinite and the chain is null recurrent. What irreducibility does guarantee is that if a stationary distribution exists, it's unique.

Positive recurrence

A state $i$ is positive recurrent if the expected return time $m_i = E[T_i \mid X_0 = i]$ is finite, where $T_i$ is the first return time to state $i$. In an irreducible chain, either all states are positive recurrent or none are.

Positive recurrence is the condition that actually ensures existence. For an irreducible, positive recurrent chain, the unique stationary distribution is given by:

$\pi_i = \frac{1}{m_i}$

This formula connects the stationary probability of a state directly to how quickly the chain returns to it. States you visit more frequently get higher stationary probability.

For finite-state irreducible chains, positive recurrence is automatic (you always return in finite expected time), so a stationary distribution always exists.

Aperiodicity

A state has period $d$ if returns to that state can only happen at times that are multiples of $d$, and $d$ is the largest such integer. A state is aperiodic if $d = 1$. In an irreducible chain, all states share the same period.

Aperiodicity is not required for the stationary distribution to exist. A periodic, irreducible, positive recurrent chain still has a unique stationary distribution. What aperiodicity controls is convergence: whether $P^n(i,j) \to \pi_j$ as $n \to \infty$. Without aperiodicity, the chain cycles and $P^n$ doesn't converge, even though $\pi$ still exists and still describes the time-average behavior.

Computation of stationary distributions

Solving the balance equations

To find $\pi$ directly, solve the linear system $\pi P = \pi$ subject to $\sum_i \pi_i = 1$.

1. Rewrite $\pi P = \pi$ as $\pi(P - I) = 0$, where $I$ is the identity matrix.

2. This gives you $n$ equations in $n$ unknowns, but they're linearly dependent (the rows of $P - I$ don't have full rank).

3. Drop any one of the $n$ equations and replace it with the normalization constraint $\sum_i \pi_i = 1$.

4. Solve the resulting $n \times n$ system.

Example: Suppose $P = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}$. The equation $\pi P = \pi$ gives:

• $0.7\pi_1 + 0.4\pi_2 = \pi_1 \implies -0.3\pi_1 + 0.4\pi_2 = 0$
• Combined with $\pi_1 + \pi_2 = 1$

From the first equation: $\pi_2 = \frac{0.3}{0.4}\pi_1 = 0.75\pi_1$. Substituting into the normalization: $\pi_1 + 0.75\pi_1 = 1$, so $\pi_1 = \frac{4}{7} \approx 0.571$ and $\pi_2 = \frac{3}{7} \approx 0.429$.

Detailed balance (reversibility shortcut)

If you can find $\pi$ satisfying the detailed balance equations:

$\pi_i P_{ij} = \pi_j P_{ji} \quad \text{for all } i, j$

then $\pi$ is automatically a stationary distribution (after normalizing). Detailed balance says the probability flow from $i$ to $j$ equals the flow from $j$ to $i$. This is a stronger condition than the global balance equations, but when it holds, it often makes computation much easier since you can solve pairwise rather than simultaneously.

Power method for approximation

When the state space is large, solving the linear system directly can be expensive. The power method offers an iterative alternative:

1. Choose any initial distribution $\pi^{(0)}$.
2. Compute $\pi^{(k+1)} = \pi^{(k)} P$ at each iteration.
3. Repeat until $\|\pi^{(k+1)} - \pi^{(k)}\|$ is below your desired tolerance.

For an irreducible, aperiodic chain, this converges to $\pi$ regardless of the starting distribution. The rate of convergence depends on the second-largest eigenvalue of $P$ in absolute value: the closer it is to 1, the slower convergence will be.

Limiting distributions vs. stationary distributions

These two concepts are related but not identical, and confusing them is a common mistake.

• A stationary distribution $\pi$ satisfies $\pi P = \pi$. It describes a fixed point.
• A limiting distribution is $\lim_{n \to \infty} \mu P^n$, where $\mu$ is some initial distribution. It describes convergence behavior.

When they coincide

If the chain is irreducible and aperiodic (and positive recurrent), then the limiting distribution exists and equals the unique stationary distribution, regardless of the initial distribution $\mu$. That is:

$\lim_{n \to \infty} P^n(i,j) = \pi_j \quad \text{for all } i, j$

When they differ

• Periodic chains: The stationary distribution exists, but $P^n(i,j)$ oscillates rather than converging. The time-average $\frac{1}{N}\sum_{n=0}^{N-1} P^n(i,j) \to \pi_j$, but the pointwise limit does not exist.
• Reducible chains: The limiting behavior depends on the starting state, and there may be multiple stationary distributions.

Applications of stationary distributions

Queueing theory

In a stable queue (arrival rate less than service rate), the system reaches a steady state described by a stationary distribution. For the M/M/1 queue with arrival rate $\lambda$ and service rate $\mu$ (where $\rho = \lambda/\mu < 1$), the stationary distribution over the number of customers $n$ in the system is geometric:

$\pi_n = (1 - \rho)\rho^n, \quad n = 0, 1, 2, \dots$

From this you can derive performance metrics like average queue length ($\rho/(1-\rho)$) and average waiting time via Little's law.

PageRank algorithm

Google's original PageRank models a "random surfer" clicking links as a Markov chain. States are web pages, and transitions follow outgoing links uniformly at random. To ensure irreducibility and aperiodicity, the model adds a damping factor $\alpha$ (typically 0.85): at each step, with probability $\alpha$ the surfer follows a link, and with probability $1 - \alpha$ they jump to a uniformly random page.

The stationary distribution of this modified chain assigns each page its PageRank score. Pages that are linked to by many important pages get higher stationary probability, which is why the algorithm captures a notion of "importance."

MCMC and statistical sampling

Markov Chain Monte Carlo methods (like the Metropolis-Hastings algorithm) construct a Markov chain whose stationary distribution is a target distribution you want to sample from. By running the chain long enough, the samples approximate draws from the target. The detailed balance condition is used to design the transition probabilities so that the desired distribution is indeed stationary.