Markov Chains: Transition Matrices

SECTION 1

Historical Context & Motivation

The idea that a system's future depends only on its present state — not on the path it took to arrive there — is deceptively simple, yet it underpins an enormous range of modern applications. Markov chains formalize this notion by describing sequences of random events in which the probability of each event depends solely on the state attained in the previous step. The mathematical machinery that makes these chains computationally tractable is the transition matrix, a square matrix whose entries encode every one-step probability in the system. Understanding how this framework developed helps us appreciate why it remains central to fields as diverse as genetics, economics, information retrieval, and artificial intelligence.

1906

Andrey Markov's Original Paper

Russian mathematician Andrey Markov introduced dependent random variables with the memoryless property, analyzing sequences of vowels and consonants in Pushkin's Eugene Onegin to demonstrate that probability theory could handle dependent trials.

1936

Kolmogorov's Axiomatic Framework

Andrey Kolmogorov placed Markov chains on rigorous measure-theoretic foundations, extending the theory to continuous-time processes and establishing convergence conditions for ergodic chains.

1948

Shannon's Information Theory

Claude Shannon used Markov chains to model the statistical structure of language in A Mathematical Theory of Communication, laying the groundwork for data compression and error-correcting codes.

1998

Google's PageRank Algorithm

Larry Page and Sergey Brin modeled a random web surfer as a Markov chain whose stationary distribution ranks every page on the internet — a direct, large-scale application of transition matrices.

2010s

MCMC and Machine Learning

Markov Chain Monte Carlo (MCMC) methods became indispensable in Bayesian statistics and deep generative models, powering modern AI research and computational biology.

The central question that transition matrices answer is this: given a system that moves randomly among a finite set of states according to fixed probabilities, how can we efficiently compute the likelihood of being in any particular state after n steps, and what does the system's behavior look like in the long run? Matrix algebra transforms this potentially intractable combinatorial problem into straightforward matrix multiplication.

SECTION 2

Core Principles & Definitions

Before diving into computations, it is essential to establish the foundational vocabulary and structural constraints that govern every finite Markov chain. These principles ensure that the transition matrix is well-defined and that the probabilistic interpretation remains consistent across all calculations.

State Space

A finite set S = {s₁, s₂, …, s_n} of mutually exclusive outcomes. At every discrete time step the system occupies exactly one state.

Markov (Memoryless) Property

The probability of transitioning to any future state depends only on the current state, not on the sequence of states that preceded it: P(X_n+1 | X_n, …, X₀) = P(X_n+1 | X_n).

Transition Probabilities

Each entry p_ij represents the probability of moving from state i to state j in one step. All probabilities satisfy 0 ≤ p_ij ≤ 1.

Stochastic Matrix Constraint

Each row of the transition matrix must sum to exactly 1, because from any state the system must go somewhere (including possibly staying put). A matrix with this property is called row-stochastic.

Initial State Distribution

A row vector π⁽⁰⁾ = [π₁, π₂, …, π_n] describes the probability of the system starting in each state. Together with the transition matrix, it fully determines all future distributions.

✦ KEY TAKEAWAY

Think of a transition matrix like a GPS at every intersection in a city: no matter how you arrived at the current intersection, the GPS gives you the same set of turn probabilities. The Markov property is precisely this 'amnesia' — the system's next move depends only on where it is, not where it has been. This simplification is what makes matrix methods so powerful: instead of tracking exponentially many histories, you only need to track the current state distribution and multiply by a single matrix.

SECTION 3

Visual Explanation: State Transition Diagram

The most intuitive representation of a Markov chain is a state transition diagram — a directed graph in which each node represents a state and each weighted arrow represents a transition probability. The diagram below illustrates a three-state Markov chain for a simplified weather model with states Sunny (S), Cloudy (C), and Rainy (R). Each arrow is labeled with the probability of that particular transition, and the self-loops indicate the probability that the weather remains unchanged from one day to the next.

Each node represents a weather state. Arrows show one-step transition probabilities; for instance, the arrow from S to C labeled 0.3 means P(Cloudy tomorrow | Sunny today) = 0.3. Self-loops (e.g., S → S at 0.6) represent the probability of remaining in the same state. Verify that all outgoing arrows from any single node sum to 1.

Reading the diagram carefully, notice that from state Sunny the outgoing probabilities are 0.6 + 0.3 + 0.1 = 1.0, confirming the row-stochastic constraint. The same check holds for Cloudy (0.4 + 0.3 + 0.3 = 1.0) and Rainy (0.3 + 0.2 + 0.5 = 1.0). This graphical representation translates directly into the rows of the transition matrix that we formalize in the next section.

SECTION 4

Mathematical Framework

We now translate the state transition diagram into the algebraic language of matrices. The power of this representation is that multi-step transition probabilities reduce to matrix powers, and long-run behavior can be extracted from the matrix's spectral properties.

TRANSITION MATRIX

P = [ p_ij ] where p_ij = P(X_{n+1} = s_j | X_n = s_i)

P is an n × n matrix. Row i contains the transition probabilities out of state s_i. The entry in row i, column j gives the one-step probability of moving from state i to state j.

For our weather example, the transition matrix is:

WEATHER TRANSITION MATRIX

P = ⎡ 0.6 0.3 0.1 ⎤ ⎢ 0.4 0.3 0.3 ⎥ ⎣ 0.3 0.2 0.5 ⎦

Row 1 = Sunny, Row 2 = Cloudy, Row 3 = Rainy. Each row sums to 1.

n-STEP DISTRIBUTION

π⁽ⁿ⁾ = π⁽⁰⁾ × Pⁿ

π⁽⁰⁾ is the initial state distribution (a row vector), P is the transition matrix, and Pⁿ denotes the matrix P multiplied by itself n times. The resulting row vector π⁽ⁿ⁾ gives the probability of being in each state after n steps.

STEADY-STATE (STATIONARY) DISTRIBUTION

π = π × P subject to Σ πᵢ = 1

A row vector π that satisfies π = πP is called the stationary distribution. For an ergodic (irreducible and aperiodic) Markov chain, this distribution is unique and represents the long-run proportion of time the system spends in each state, regardless of the initial distribution.

⚠ Row-Stochastic vs. Column-Stochastic Convention

Many finite mathematics textbooks use the row-stochastic convention (rows sum to 1, state vector is a row vector multiplied on the left). Some probability and statistics references use the column-stochastic convention (columns sum to 1, state vector is a column vector multiplied on the right). Both are valid; just be consistent. This lesson follows the row-stochastic convention throughout.

SECTION 5

Classifying States & Chains

Not all Markov chains behave the same way in the long run. The classification of states determines whether a unique stationary distribution exists and whether the chain converges to it. Two properties are decisive: irreducibility (every state can be reached from every other state) and aperiodicity (the system does not cycle through states in a fixed period). A chain possessing both properties is called ergodic, and the Fundamental Theorem of Markov Chains guarantees it has a unique stationary distribution to which all initial distributions converge.

Four types of Markov chains. Top-left: an ergodic chain where every state communicates and has a self-loop preventing strict periodicity. Top-right: an absorbing chain with state F as an absorbing state (self-loop probability 1.0). Bottom-left: a periodic chain cycling between G and H with period 2. Bottom-right: a reducible chain where state I cannot be reached from states J or K.

Key state and chain classifications

Property	Definition	Consequence
Irreducible	Every state is reachable from every other state in some finite number of steps.	All states belong to a single communicating class; the chain cannot get 'trapped' in a subset.
Aperiodic	The greatest common divisor of all return times to any state is 1.	The chain does not cycle deterministically; Pⁿ converges as n → ∞.
Ergodic	The chain is both irreducible and aperiodic.	A unique stationary distribution π exists, and π⁽ⁿ⁾ → π for every initial distribution.
Absorbing	A state s is absorbing if p_ss = 1 (once entered, never left).	The chain is reducible. Probability of eventual absorption is 1 if every transient state can reach an absorbing state.

SECTION 6

Worked Example: Two-Step Forecast & Steady State

Suppose today is Sunny. Using the weather transition matrix from Section 3, we will (a) find the probability distribution two days from now, and (b) compute the long-run stationary distribution.

Two-Step Forecast & Steady-State Distribution

Step 1 — Set Up the Initial DistributionSince today is Sunny, the initial state vector is π⁽⁰⁾ = [1, 0, 0], where the entries correspond to [Sunny, Cloudy, Rainy].

π⁽⁰⁾ = [1, 0, 0]

Step 2 — Compute the One-Step DistributionMultiply π⁽⁰⁾ by P: π⁽¹⁾ = [1, 0, 0] × P = [0.6, 0.3, 0.1]. This is simply the first row of P, because we started with certainty in state 1.

π⁽¹⁾ = [0.6, 0.3, 0.1]

Step 3 — Compute the Two-Step DistributionMultiply π⁽¹⁾ by P: π⁽²⁾ = [0.6, 0.3, 0.1] × P. Performing the matrix–vector multiplication: entry 1 = 0.6(0.6) + 0.3(0.4) + 0.1(0.3) = 0.36 + 0.12 + 0.03 = 0.51; entry 2 = 0.6(0.3) + 0.3(0.3) + 0.1(0.2) = 0.18 + 0.09 + 0.02 = 0.29; entry 3 = 0.6(0.1) + 0.3(0.3) + 0.1(0.5) = 0.06 + 0.09 + 0.05 = 0.20.

π⁽²⁾ = [0.51, 0.29, 0.20]

Step 4 — Set Up the Steady-State EquationsWe need π = πP and π₁ + π₂ + π₃ = 1. Writing out π = πP yields three equations: π₁ = 0.6π₁ + 0.4π₂ + 0.3π₃, π₂ = 0.3π₁ + 0.3π₂ + 0.2π₃, π₃ = 0.1π₁ + 0.3π₂ + 0.5π₃. Rearranging (subtracting πᵢ from both sides): −0.4π₁ + 0.4π₂ + 0.3π₃ = 0, 0.3π₁ − 0.7π₂ + 0.2π₃ = 0, 0.1π₁ + 0.3π₂ − 0.5π₃ = 0.

Step 5 — Solve the SystemFrom equation 1: 0.4π₁ = 0.4π₂ + 0.3π₃ → π₁ = π₂ + 0.75π₃. Substituting into equation 2: 0.3(π₂ + 0.75π₃) − 0.7π₂ + 0.2π₃ = 0 → 0.3π₂ + 0.225π₃ − 0.7π₂ + 0.2π₃ = 0 → −0.4π₂ + 0.425π₃ = 0 → π₂ = (0.425/0.4)π₃ = 1.0625π₃. Then π₁ = 1.0625π₃ + 0.75π₃ = 1.8125π₃. Using π₁ + π₂ + π₃ = 1: 1.8125π₃ + 1.0625π₃ + π₃ = 3.875π₃ = 1, so π₃ = 1/3.875 ≈ 0.2581. Then π₂ ≈ 0.2742 and π₁ ≈ 0.4677.

π ≈ [0.468, 0.274, 0.258]

Step 6 — Interpret the ResultIn the long run, regardless of today's weather, the system will be Sunny about 46.8% of days, Cloudy about 27.4% of days, and Rainy about 25.8% of days. The two-step distribution [0.51, 0.29, 0.20] is already trending toward this steady state, and repeated multiplication will bring it ever closer.

SECTION 7

Strengths, Limitations, and Modeling Considerations

Markov chain models with finite state spaces and fixed transition matrices are remarkably versatile, but their assumptions can also be restrictive. Understanding where the model excels and where it breaks down is essential for responsible application.

Strengths and limitations of finite Markov chain models

Strengths	Limitations
Compact representation: an n-state system requires only an n × n matrix, making storage and computation efficient.	The memoryless assumption may be unrealistic for systems with long-range dependencies (e.g., stock prices influenced by trends).
Multi-step forecasting reduces to matrix exponentiation — standard, well-optimized operations in linear algebra libraries.	Transition probabilities are assumed constant (time-homogeneous). Seasonal or evolving systems violate this.
Steady-state analysis provides powerful long-run insights without simulation, via eigenvalue methods.	State space must be finite (or countable) for the matrix framework; continuous state spaces require different tools (e.g., kernel density methods).
Easily interpretable: transition diagrams and matrices convey the model's structure transparently.	Estimating accurate transition probabilities requires substantial data; small samples can yield unreliable matrices.

✦ KEY TAKEAWAY

A finite Markov chain is like a well-calibrated weather station that issues tomorrow's forecast based solely on today's conditions, ignoring all previous days. When tomorrow's weather truly depends primarily on today's — a reasonable first approximation in many meteorological contexts — this simplification yields fast, accurate predictions. But if next week's weather depends on a persistent pattern that began several days ago, the memoryless model misses that structure. Recognizing this boundary is what separates a thoughtful modeler from someone who merely runs the math.

SECTION 8

Connection to Advanced Theory

The finite, discrete-time Markov chain studied in this lesson is the entry point to a rich hierarchy of stochastic models. As you progress through probability and applied mathematics, you will encounter extensions that relax the constraints we have imposed here. The table below maps the key generalizations and indicates where the transition matrix framework either extends naturally or requires fundamentally new tools.

From finite Markov chains to advanced stochastic models

Feature	This Lesson	Advanced Extension
Time	Discrete steps (n = 0, 1, 2, …)	Continuous-time Markov chains use a rate matrix Q and matrix exponential e^Qt for transition probabilities over any time interval t.
State space	Finite: n states, n × n matrix	Countably infinite (birth-death chains) or continuous (Markov diffusion processes governed by Fokker–Planck equations).
Transition rule	Fixed (time-homogeneous) matrix P	Time-inhomogeneous chains use a sequence P⁽¹⁾, P⁽²⁾, … of different matrices at each step.
Memory	First-order: depends on current state only	Higher-order Markov chains condition on the last k states; Hidden Markov Models (HMMs) introduce unobservable states.
Computational use	Direct multiplication Pⁿ for forecasts	MCMC algorithms (Metropolis–Hastings, Gibbs sampling) construct chains whose stationary distribution matches a target distribution for Bayesian inference.

In a linear algebra course, you will see that the stationary distribution π is the left eigenvector of P corresponding to eigenvalue λ = 1. The Perron–Frobenius theorem guarantees that for a positive (ergodic) matrix, the eigenvalue 1 is dominant and simple, ensuring uniqueness of π and geometric convergence of Pⁿ. The second-largest eigenvalue modulus controls the mixing rate — how quickly the chain 'forgets' its initial state — a quantity of immense practical importance in MCMC sampling.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

A 4 × 4 matrix has all non-negative entries and every row sums to 1. One of the diagonal entries is 1 and the rest of that row's entries are 0. What can you conclude about the corresponding state? Is the overall chain necessarily ergodic? Explain your reasoning.

PROBLEM 2 — BASIC CALCULATION

Consider a two-state Markov chain with transition matrix P = [[0.7, 0.3], [0.4, 0.6]]. If the system starts in state 1, find the state distribution after two steps, π⁽²⁾.

PROBLEM 3 — INTERMEDIATE

For the same two-state chain P = [[0.7, 0.3], [0.4, 0.6]], find the stationary distribution π by solving π = πP together with π₁ + π₂ = 1.

PROBLEM 4 — APPLIED

A ride-sharing company classifies each customer as Active (A), Inactive (I), or Churned (C). Monthly transition probabilities are: P(A→A) = 0.8, P(A→I) = 0.15, P(A→C) = 0.05; P(I→A) = 0.3, P(I→I) = 0.5, P(I→C) = 0.2; P(C→A) = 0, P(C→I) = 0, P(C→C) = 1. Currently 60% of users are Active, 30% Inactive, and 10% Churned. What fraction of users are in each category after one month? Is this chain ergodic?

PROBLEM 5 — CRITICAL THINKING

Prove that the product of two row-stochastic matrices is also row-stochastic. Then explain why this result is essential for the interpretation of Pⁿ as an n-step transition matrix.

SUMMARY

Lesson Summary

A Markov chain models a system that transitions among a finite set of states according to fixed probabilities, with the defining memoryless (Markov) property ensuring that the next state depends only on the current one. All one-step transition probabilities are organized into a row-stochastic transition matrix P, where each entry p_ij is non-negative and each row sums to 1. The state distribution after n steps is computed via π⁽ⁿ⁾ = π⁽⁰⁾Pⁿ, reducing multi-step forecasting to matrix multiplication.

When a chain is ergodic (both irreducible and aperiodic), a unique stationary distribution π exists, satisfying π = πP with Σπᵢ = 1. This vector describes the long-run proportion of time spent in each state and is the left eigenvector of P for eigenvalue 1. Chains that are absorbing, periodic, or reducible require separate analysis but build on the same matrix framework, making transition matrices the indispensable tool for all finite stochastic modeling.