Markov Chains: Steady State — Long-run behavior and...

SECTION 1

Historical Context & Motivation

The study of random processes that evolve over time has a rich mathematical heritage, and Markov chains stand at the center of this tradition. The concept arose from a deceptively simple question: if a system moves randomly between a finite number of states, and each transition depends only on the current state, what happens after a very long time? The answer — that many such systems settle into a predictable steady-state distribution — has profound consequences for fields ranging from economics and genetics to information retrieval and queuing theory. Understanding this long-run behavior transforms Markov chains from a tool for one-step prediction into a framework for analyzing equilibrium phenomena in stochastic systems.

1906

Markov's Original Formulation

Andrey Markov introduces chains of linked random variables to study sequences of dependent events, challenging the prevailing assumption that the law of large numbers requires independence.

1936

Kolmogorov's Foundational Work

Andrey Kolmogorov formalizes the axiomatic foundations of probability theory and establishes rigorous conditions for the convergence of Markov chains to stationary distributions.

1953

Metropolis Algorithm

Nicholas Metropolis and collaborators develop Monte Carlo sampling methods that exploit the convergence properties of Markov chains, laying groundwork for modern computational statistics.

1998

Google PageRank

Sergey Brin and Larry Page model the web as a Markov chain and use its steady-state vector to rank pages — a direct, billion-dollar application of steady-state theory.

The central question motivating steady-state analysis is both elegant and practical: given a system that evolves according to fixed probabilistic rules, does the distribution over states eventually stabilize, and if so, what is that equilibrium distribution? The answer connects linear algebra — specifically eigenvalue problems — with probability theory, producing one of the most widely applicable results in finite mathematics.

SECTION 2

Core Principles & Definitions

Before exploring steady-state behavior, it is essential to establish the building blocks. A Markov chain is defined by a finite set of states and a transition matrix P whose entry p_ij gives the probability of moving from state i to state j in one step. The Markov property asserts that the future depends only on the present state, not on how the system arrived there — a property often called memorylessness. All rows of P must sum to 1, making P a stochastic matrix. With these definitions in hand, we can formalize the conditions under which long-run behavior stabilizes.

Transition Matrix P

A square matrix whose entry p_ij ≥ 0 represents the one-step probability from state i to state j. Each row sums to 1.

State Distribution Vector

A row vector q⁽ⁿ⁾ whose i-th entry is the probability of being in state i after n steps. Evolution: q⁽ⁿ⁺¹⁾ = q⁽ⁿ⁾P.

Regular Chain

A Markov chain is regular if some power Pⁿ has all strictly positive entries. Regularity implies the chain is both irreducible (every state reachable from every other) and aperiodic (no forced cycling). In finite Markov chain theory, a chain that is irreducible and aperiodic is also called ergodic; for finite chains these properties together are equivalent to regularity.

Steady-State Vector π

A probability vector satisfying πP = π. It represents the long-run proportion of time spent in each state, independent of the initial distribution.

Convergence Theorem

For a regular Markov chain, Pⁿ → a matrix with identical rows equal to π as n → ∞. The steady-state vector is unique.

✦ KEY TAKEAWAY

Think of a steady-state distribution like the long-run traffic pattern in a city's road network. Even if everyone starts at different locations in the morning, after enough hours the fraction of drivers on each road segment stabilizes — regardless of starting positions. The steady-state vector π captures exactly this kind of emergent equilibrium in any regular Markov chain.

SECTION 3

Visual Explanation — State Transition Diagram

A state transition diagram provides the most intuitive visualization of a Markov chain. Each state is represented as a node, and directed edges carry the transition probabilities. The following diagram illustrates a three-state Markov chain — the same system we will analyze algebraically in later sections. Notice how every state has outgoing edges whose probabilities sum to 1, and every state is reachable from every other state, confirming that the chain is regular.

Three-state Markov chain with transition probabilities labeled on each directed edge. Self-loops represent the probability of remaining in the same state. Outgoing probabilities from each state sum to 1. This chain is regular because every state can reach every other state.

The transition matrix corresponding to this diagram is read row by row: the first row contains the probabilities leaving S₁ (0.5, 0.3, 0.2), the second row contains those leaving S₂ (0.4, 0.4, 0.2), and the third row contains those leaving S₃ (0.3, 0.5, 0.2). Because every entry of P is already positive, P¹ itself has all positive entries, which means this chain is regular and possesses a unique steady-state vector.

SECTION 4

Mathematical Framework

Finding the steady-state vector π reduces to solving a system of linear equations. Because π must be a fixed point of the transition operator, it satisfies the steady-state equation together with the normalization constraint that the components of π sum to 1. This pair of conditions yields a system whose unique solution can be obtained with standard row-reduction techniques from linear algebra.

EVOLUTION RULE

q⁽ⁿ⁺¹⁾ = q⁽ⁿ⁾ · P

q⁽ⁿ⁾ is the row distribution vector after n steps; P is the transition matrix. Multiplying by P advances the system by one time step.

STEADY-STATE EQUATION

πP = π

The steady-state vector π is a left eigenvector of P corresponding to eigenvalue 1. Equivalently, π(P − I) = 0, where I is the identity matrix.

NORMALIZATION CONSTRAINT

π₁ + π₂ + ⋯ + πₙ = 1

Since π is a probability distribution, its entries must sum to 1. This constraint replaces one of the dependent equations in π(P − I) = 0 to produce a unique solution.

CONVERGENCE

lim (n→∞) Pⁿ = W, where every row of W equals π

For a regular chain, powers of P converge to a matrix W whose every row is the steady-state vector π. This means the long-run distribution is independent of the initial state.

💡 Why Replace an Equation?

The system πP = π is homogeneous — its coefficient matrix (P − I)ᵀ is singular because P always has eigenvalue 1. This means the system has infinitely many solutions along a line through the origin. Replacing any one equation with π₁ + π₂ + ⋯ + πₙ = 1 pins down the unique probability vector on that line. This is the standard technique for converting a homogeneous eigenvalue problem into a determinate system.

SECTION 5

Convergence Behavior — Watching Distributions Stabilize

To build intuition for convergence, consider tracking the distribution vector q⁽ⁿ⁾ over successive steps. The diagram below plots the probability of being in each state against the step number for the three-state chain from Section 3, starting from the initial distribution q⁽⁰⁾ = (1, 0, 0) — that is, the system begins entirely in state S₁. Despite this extreme starting condition, the distribution converges rapidly to the steady-state vector within roughly 3–4 steps.

State probability trajectories starting from q⁽⁰⁾ = (1, 0, 0). The cyan, violet, and pink curves represent the probability of occupying S₁, S₂, and S₃ respectively. Dashed horizontal lines mark the steady-state values π ≈ (0.422, 0.378, 0.200). Convergence is essentially complete by step 3–4.

The key observation from this visualization is that convergence is geometric — the distance between q⁽ⁿ⁾ and π shrinks by a roughly constant factor at each step. This factor is governed by the second-largest eigenvalue magnitude |λ₂| of the transition matrix P. A smaller |λ₂| means faster convergence. For our three-state chain, convergence is rapid because the gap between λ₁ = 1 and the magnitudes of the remaining eigenvalues is substantial. Regardless of whether the system starts in S₁, S₂, or S₃, or any mixture thereof, it reaches the same equilibrium — a hallmark of regular Markov chains.

Distribution vector q⁽ⁿ⁾ converging to the steady-state vector π = (19/45, 17/45, 9/45)

Step n	q₁⁽ⁿ⁾	q₂⁽ⁿ⁾	q₃⁽ⁿ⁾
0	1.000	0.000	0.000
1	0.500	0.300	0.200
2	0.430	0.370	0.200
3	0.423	0.377	0.200
5	0.422	0.378	0.200
∞ (π)	19/45 ≈ 0.422	17/45 ≈ 0.378	9/45 = 0.200

SECTION 6

Worked Example — Finding the Steady-State Vector

We now compute the exact steady-state vector for the three-state chain introduced in Section 3. The transition matrix is:

TRANSITION MATRIX

P = [ 0.5 0.3 0.2 ; 0.4 0.4 0.2 ; 0.3 0.5 0.2 ]

Rows correspond to states S₁, S₂, S₃. Each row sums to 1.

Compute the Steady-State Vector π = (π₁, π₂, π₃)

Step 1 — Write πP = π as a systemExpanding the matrix equation πP = π with π = (π₁, π₂, π₃) gives three equations: (1) 0.5π₁ + 0.4π₂ + 0.3π₃ = π₁, (2) 0.3π₁ + 0.4π₂ + 0.5π₃ = π₂, (3) 0.2π₁ + 0.2π₂ + 0.2π₃ = π₃. Note that we multiply π (a row vector) on the right by P, so column j of P gives the coefficient of πⱼ in the resulting equation for state j.

Step 2 — Rearrange each equationMoving the right-hand side to the left: (1) −0.5π₁ + 0.4π₂ + 0.3π₃ = 0, (2) 0.3π₁ − 0.6π₂ + 0.5π₃ = 0, (3) 0.2π₁ + 0.2π₂ − 0.8π₃ = 0. These are the rows of π(P − I) = 0. Note that these three equations are linearly dependent — any two determine a one-dimensional solution space.

Step 3 — Replace one equation with normalizationDrop equation (3) and replace it with the normalization constraint: π₁ + π₂ + π₃ = 1. The system is now: −0.5π₁ + 0.4π₂ + 0.3π₃ = 0, 0.3π₁ − 0.6π₂ + 0.5π₃ = 0, π₁ + π₂ + π₃ = 1.

Step 4 — Solve by eliminationMultiply equations (1) and (2) through by 10 to clear decimals: (1) −5π₁ + 4π₂ + 3π₃ = 0, giving 5π₁ = 4π₂ + 3π₃. (2) 3π₁ − 6π₂ + 5π₃ = 0, giving 3π₁ = 6π₂ − 5π₃. Eliminate π₁ by multiplying equation (1) by 3 and equation (2) by 5: 15π₁ = 12π₂ + 9π₃ and 15π₁ = 30π₂ − 25π₃. Setting these equal: 12π₂ + 9π₃ = 30π₂ − 25π₃, so 34π₃ = 18π₂, giving π₂ = (17/9)π₃. Substituting back into 5π₁ = 4π₂ + 3π₃: 5π₁ = 4(17/9)π₃ + 3π₃ = (68/9 + 27/9)π₃ = (95/9)π₃, so π₁ = (19/9)π₃.

π₁ = (19/9)π₃, π₂ = (17/9)π₃

Step 5 — Apply normalizationSubstituting into π₁ + π₂ + π₃ = 1: (19/9)π₃ + (17/9)π₃ + (9/9)π₃ = 1 → (45/9)π₃ = 1 → 5π₃ = 1 → π₃ = 1/5 = 9/45. Then π₂ = (17/9)(9/45) = 17/45, and π₁ = (19/9)(9/45) = 19/45.

π = (19/45, 17/45, 9/45) ≈ (0.4222, 0.3778, 0.2000)

Step 6 — VerifyCheck πP = π: First component: 0.5(19/45) + 0.4(17/45) + 0.3(9/45) = (9.5 + 6.8 + 2.7)/45 = 19/45 ✓. Second component: 0.3(19/45) + 0.4(17/45) + 0.5(9/45) = (5.7 + 6.8 + 4.5)/45 = 17/45 ✓. Third component: 0.2(19/45) + 0.2(17/45) + 0.2(9/45) = 0.2(45/45) = 9/45 ✓. The normalization also checks: 19/45 + 17/45 + 9/45 = 45/45 = 1 ✓.

Verified: πP = π and π₁ + π₂ + π₃ = 1.

📌 Steady-State Result

The exact steady-state vector is π = (19/45, 17/45, 9/45) ≈ (0.422, 0.378, 0.200). This result is confirmed by the numerical iteration table in Section 5, which shows the distribution converging to these same values by step 3. In the long run, the system spends about 42.2% of its time in S₁, 37.8% in S₂, and exactly 20% in S₃ — regardless of where it started.

SECTION 7

Conditions, Strengths & Limitations

Not every Markov chain possesses a unique steady-state vector. The convergence theorem applies specifically to regular chains, and certain structural properties — periodicity, absorbing states, and reducibility — can prevent convergence to a single equilibrium. The following table summarizes the key conditions and their implications for steady-state analysis.

Key structural properties affecting steady-state existence and uniqueness

Property	Definition	Impact on Steady State
Irreducible	Every state can reach every other state (possibly in multiple steps).	Necessary for a unique stationary distribution. If the chain is reducible, different communicating classes may have separate steady states.
Aperiodic	The GCD of return times to any state is 1; the chain does not cycle deterministically.	Required for Pⁿ to converge. A periodic chain has a stationary distribution but Pⁿ oscillates and does not settle to a fixed limit.
Regular	Some power Pⁿ has all positive entries (implies irreducible and aperiodic). For finite chains, a regular chain is also called ergodic.	Sufficient condition for unique steady state. Pⁿ converges to a rank-1 matrix with identical rows equal to π.
Absorbing states	A state i with p_ii = 1; once entered, the system never leaves.	The chain is not regular. Long-run behavior concentrates entirely in absorbing states; analyzed via absorbing chain theory instead.
Self-loops	Positive diagonal entries p_ii > 0 for at least one state.	Helpful: a self-loop on any state automatically breaks periodicity, simplifying verification of regularity.

✦ KEY TAKEAWAY

Think of regularity as a well-mixed cocktail: if every ingredient (state) can eventually diffuse into every part of the glass (reach every other state) and there is no rigid cycle forcing a clockwise-only rotation, then the mixture reaches a uniform equilibrium. Absorbing states are like oil droplets — once material enters, it stays trapped, and the system never reaches global equilibrium. When checking whether a chain has a steady state, first test regularity by computing a few powers of P to see if all entries become positive.

SECTION 8

Connections to Advanced Theory

The introductory steady-state concepts covered in this lesson provide a foundation for several more advanced topics in stochastic processes and linear algebra. Understanding how the basic theory extends will help contextualize the significance of the steady-state vector and clarify the assumptions we have been working under.

From introductory concepts to advanced theory

Introductory Concept	Advanced Extension
Steady-state vector πP = π	Perron–Frobenius theory: guarantees the dominant eigenvalue of a positive stochastic matrix is 1 with a unique positive eigenvector.
Finite-state discrete-time chain	Continuous-time Markov chains (CTMCs): transitions governed by rate matrices Q instead of probability matrices P. Steady state satisfies πQ = 0.
Regularity ensures convergence	Mixing time analysis: quantifies how many steps are needed until the distribution is ε-close to π, using spectral gap (1 − \|λ₂\|).
Row-reduction to find π	Markov Chain Monte Carlo (MCMC): constructs chains whose steady state equals a target distribution, enabling sampling from complex probability models.
Absorbing chains excluded	Absorbing Markov chain theory: uses the fundamental matrix N = (I − Q)⁻¹ to compute expected absorption times and absorption probabilities.

Perhaps the most celebrated modern application of steady-state theory is the PageRank algorithm. Google's founders modeled the World Wide Web as a directed graph with billions of nodes, treated a hypothetical random surfer as a Markov chain, and computed the steady-state vector of the resulting (modified) transition matrix. Each page's steady-state probability became its importance score — a direct, large-scale application of the concepts in this lesson. The modification (adding a "teleportation" probability) ensures the chain is regular, illustrating how real-world systems are engineered to satisfy the convergence theorem.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain in your own words why the steady-state vector π is independent of the initial distribution q⁽⁰⁾ for a regular Markov chain. What property of the transition matrix guarantees this independence?

PROBLEM 2 — BASIC CALCULATION

A two-state Markov chain has transition matrix P = [ 0.7 0.3 ; 0.6 0.4 ]. Find the steady-state vector π = (π₁, π₂).

PROBLEM 3 — INTERMEDIATE

Consider the transition matrix P = [ 0.5 0.5 0 ; 0.25 0.5 0.25 ; 0 0.5 0.5 ]. (a) Is this chain regular? Justify your answer. (b) If it is regular, find the steady-state vector.

PROBLEM 4 — APPLIED

A market research firm models brand switching among three coffee brands A, B, C. Each month, 80% of A-drinkers stay with A, 10% switch to B, and 10% switch to C. Of B-drinkers, 20% switch to A, 70% stay with B, and 10% switch to C. Of C-drinkers, 10% switch to A, 20% switch to B, and 70% stay with C. Find the long-run market share for each brand.

PROBLEM 5 — CRITICAL THINKING

Consider the 2 × 2 transition matrix P = [ 0 1 ; 1 0 ]. (a) Is this chain irreducible? (b) Is it aperiodic? (c) Does πP = π have a solution? (d) Does Pⁿ converge as n → ∞? Reconcile your answers to (c) and (d) and explain what this reveals about the relationship between the existence of a stationary distribution and convergence.

SUMMARY

Lesson Summary

A Markov chain models a system that transitions among a finite set of states according to fixed probabilities encoded in a transition matrix P. The Markov property — memorylessness — ensures that the next state depends only on the current state. When a chain is regular (some power Pⁿ has all positive entries), the distribution q⁽ⁿ⁾ converges to a unique steady-state vector π regardless of the initial distribution.

The steady-state vector is found by solving the system πP = π subject to the normalization constraint π₁ + π₂ + ⋯ + πₙ = 1, a problem reducible to standard row reduction from linear algebra. Regularity requires both irreducibility and aperiodicity; chains with absorbing states or periodic behavior require alternative analytical tools. The steady-state concept underpins applications from PageRank and market-share modeling to MCMC sampling, making it one of the most broadly applicable results in finite mathematics.