Markov Chains
A Markov chain is a mathematical model for a system that moves through a sequence of states over time, where the probability of transitioning to the next state depends only on the current state — not on the history of how the system got there. This property is called the Markov property, or 'memorylessness.' Examples include a board game piece moving between squares, the daily weather cycling through sunny, cloudy, and rainy, or a random walk along a number line. Markov chains are described using transition matrices — square matrices where each entry gives the probability of moving from one state to another. By raising this matrix to successive powers, we can predict the probability distribution of the system after many steps. A central question is: what happens in the long run? For a special class called regular Markov chains, the distribution converges to a unique steady-state vector regardless of where the system started. Markov chains connect beautifully to linear algebra through eigenvalues and eigenvectors. The steady-state distribution turns out to be the eigenvector of the transition matrix corresponding to eigenvalue 1. This deep link between probability and linear algebra makes Markov chains one of the most powerful and elegant tools in applied mathematics, with applications ranging from Google's PageRank algorithm to genetics, economics, and machine learning.
- States and the Transition Matrix
- State Vectors and Updating
- Regular Markov Chains
- Finding the Steady-State Vector
- Eigenvalue Connection and Convergence Rate
States and the Transition Matrix
A Markov chain begins by identifying a finite set of states, say {S₁, S₂, …, Sₙ}. The transition matrix T is an n×n matrix where entry Tᵢⱼ = P(move to state j | currently in state i) — the probability of going from state i to state j. Every row must sum to 1 (since you must go somewhere), and all entries must satisfy 0 ≤ Tᵢⱼ ≤ 1. Such a matrix is called a stochastic matrix or row-stochastic matrix.
State Vectors and Updating
The current probability distribution over all states is stored in a row vector v = [v₁, v₂, …, vₙ], where vᵢ is the probability of being in state i. The entries sum to 1. After one step, the new distribution is v⁽¹⁾ = v⁽⁰⁾ T. After k steps, the distribution is v⁽ᵏ⁾ = v⁽⁰⁾ Tᵏ. This means the k-th power of the transition matrix encodes all k-step transition probabilities: (Tᵏ)ᵢⱼ gives the probability of being in state j after exactly k steps, starting from state i.
Regular Markov Chains
A Markov chain is called regular if some power Tᵏ has all positive entries — meaning it is possible to get from any state to any other state in exactly k steps. Regular chains are guaranteed to have a unique steady-state distribution π = [π₁, π₂, …, πₙ], with πᵢ > 0 and Σπᵢ = 1. No matter what the initial distribution v⁽⁰⁾ is, the sequence v⁽⁰⁾, v⁽¹⁾, v⁽²⁾, … converges to π. Absorbing Markov chains (where some states can never be left) are non-regular and behave differently.
Finding the Steady-State Vector
The steady-state vector π satisfies the equation π T = π, meaning it is unchanged by one more step of the chain. This is equivalent to π (T − I) = 0, a homogeneous linear system. Combined with the normalization condition π₁ + π₂ + ⋯ + πₙ = 1, this system has a unique solution for regular chains. In terms of eigenvalues, π T = π means π is a left eigenvector of T with eigenvalue λ = 1. The Perron-Frobenius theorem guarantees that λ = 1 is always the largest eigenvalue of a stochastic matrix, and for regular chains the corresponding eigenvector is unique.
Eigenvalue Connection and Convergence Rate
Every stochastic matrix has eigenvalue λ₁ = 1. The remaining eigenvalues λ₂, λ₃, … satisfy |λᵢ| ≤ 1. For a regular chain, |λᵢ| < 1 for i ≥ 2. Since Tᵏ can be written in terms of eigenvalues, as k → ∞ the terms involving λᵢᵏ vanish (because |λᵢ| < 1), leaving only the contribution from λ = 1. The second-largest eigenvalue |λ₂| controls how quickly convergence happens: the smaller |λ₂|, the faster the chain mixes. This is called the spectral gap, and it is critical in applications like randomized algorithms.
The Key Equation
- \pi — Steady-state (stationary) distribution (dimensionless): A row probability vector [π₁, π₂, …, πₙ] giving the long-run fraction of time spent in each state.
- T — Transition matrix (dimensionless): An n×n row-stochastic matrix where entry Tᵢⱼ is the probability of transitioning from state i to state j.
- \pi_i — Steady-state probability for state i (dimensionless): The long-run probability that the chain is found in state i; must be strictly positive for a regular chain.
Worked Example
Problem. A simple weather model has two states: Sunny (S) and Rainy (R). If it is sunny today, there is a 70% chance it is sunny tomorrow and a 30% chance it is rainy. If it is rainy today, there is a 40% chance it is sunny tomorrow and a 60% chance it is rainy. Write the transition matrix, find the steady-state distribution, and determine the probability of it being sunny after 2 days if today is sunny.
Answer. Steady-state distribution: Sunny 4/7 ≈ 57.1%, Rainy 3/7 ≈ 42.9%. Probability of sunny in 2 days (starting sunny): 61%.
Origins · 1 minAndrey Andreyevich Markov and how this was discovered
Markov introduced what we now call Markov chains in 1906 while studying sequences of dependent random variables. He was motivated partly by a desire to extend the law of large numbers beyond the case of independent events. His analysis of letter sequences in Pushkin's novel 'Eugene Onegin' was a pioneering example of applying Markov chains to real data, showing that vowels and consonants alternate in statistically predictable patterns. Markov had a famous and bitter public feud with fellow mathematician Pavel Nekrasov, who had incorrectly claimed that independence was necessary for the law of large numbers to hold. Markov invented his chains partly to prove Nekrasov wrong by providing explicit examples of dependent variables that still obeyed the law.
Related Concepts
- Stochastic and Transition Matrices — The transition matrix is the core algebraic object of a Markov chain; understanding row-stochastic matrices is essential.
- Eigenvalues and Eigenvectors — The steady-state distribution is the left eigenvector of T for eigenvalue 1; the spectral gap controls convergence speed.
- Conditional Probability — Each transition probability Tᵢⱼ is a conditional probability P(next state = j | current state = i), the building block of Markov chains.
- Matrix Multiplication — Computing k-step distributions requires multiplying the state vector by powers of the transition matrix, making matrix multiplication fundamental.
- Probability Distributions — The state vector at each time step is a discrete probability distribution over the state space, connecting Markov chains to general probability theory.