Markov Chains — Mathematics Knowledge System

Overview

A Markov chain is a stochastic process with the Markov property: the future state depends only on the present state, not the full history. Formally, it is a sequence of random variables X₀, X₁, X₂, ... taking values in a countable state space S such that P(Xₙ₊₁ = j | X₀,...,Xₙ) = P(Xₙ₊₁ = j | Xₙ). This memoryless structure allows the entire dynamics to be encoded in a transition matrix P, where Pᵢⱼ = P(Xₙ₊₁ = j | Xₙ = i). Markov chains are foundational in probability, statistics, physics, and machine learning.

Intuition

Imagine a frog hopping between lily pads labeled 1, 2, 3. At each step the frog jumps to another pad with probabilities that depend only on where it currently sits, not on how it got there. The Markov property is exactly this 'no memory' rule. The transition matrix P records all jump probabilities: Pᵢⱼ is the probability of going from pad i to pad j. Multiplying P by itself k times gives the k-step transition probabilities, so Pᵏ governs long-range behavior. Under mild conditions (irreducibility and aperiodicity), the chain forgets its initial state and settles into a unique stationary distribution π satisfying πP = π.

Formal Definition

Definition

A discrete-time Markov chain on a countable state space S with transition matrix P is defined by the Markov property and the Chapman-Kolmogorov equations.

P(X_{n+1}=j \mid X_0,\ldots,X_n) = P(X_{n+1}=j \mid X_n) = P_{ij}

Markov property

P_{ij} \ge 0, \quad \sum_{j \in S} P_{ij} = 1 \quad \forall\, i

Stochastic matrix conditions

P^{(n)}_{ij} = P(X_n = j \mid X_0 = i) = (P^n)_{ij}

n-step transition probabilities

P^{(m+n)}_{ij} = \sum_{k \in S} P^{(m)}_{ik} P^{(n)}_{kj}

Chapman-Kolmogorov equation

\pi_j = \sum_{i \in S} \pi_i P_{ij}, \quad \sum_j \pi_j = 1

Stationary distribution

Notation

Notation	Meaning
$P$	Transition matrix with entries Pᵢⱼ = P(Xₙ₊₁ = j \| Xₙ = i)
$\pi$	Stationary (invariant) distribution vector satisfying πP = π
$P^{(n)}$	n-step transition matrix, equal to the n-th matrix power Pⁿ
$\mu_i$	Mean return time to state i; equals 1/πᵢ for a positive recurrent state

Theorems

Theorem 1: Theorem 1

\text{ An irreducible, aperiodic, positive-recurrent Markov chain has a unique stationary distribution } \pi \text{ and } P^n_{ ij } \to \pi_j \text{ as } n \to \infty \text{ for all } i,j.

Theorem 2: Theorem 2

\text{ For all states } i,j \in S \text{ and integers } m,n \ge 0{ : } \quad P^{ (m+n) }_{ ij } = \sum_{ k \in S } P^{ (m) }_{ ik } P^{ (n) }_{ kj }.

Theorem 3: Theorem 3

\text{ For an irreducible positive-recurrent Markov chain, the mean recurrence time of state } i \text{ is } \mu_i = 1/\pi_i.

Worked Examples

1
Set up πP = π with π₁ + π₂ = 1.
$\pi_1 = 0.7\pi_1 + 0.4\pi_2, \quad \pi_2 = 0.3\pi_1 + 0.6\pi_2$
2
From the first equation: 0.3π₁ = 0.4π₂, so π₁/π₂ = 4/3.
$0.3\pi_1 = 0.4\pi_2 \implies \pi_1 = \tfrac{4}{3}\pi_2$
3
Normalise: π₁ + π₂ = 1 gives π₂ = 3/7, π₁ = 4/7.
$\pi_1 = \frac{4}{7}, \quad \pi_2 = \frac{3}{7}$

✓ Answer

The stationary distribution is π = (4/7, 3/7).

Practice Problems

Easyfree response

A Markov chain on {1,2,3} has P₁₂ = 1, P₂₁ = P₂₃ = 1/2, P₃₂ = 1. Is the chain irreducible? Find its stationary distribution.

Mediumapplication

Explain why an irreducible Markov chain on a finite state space is always positive-recurrent, and state what this implies about the long-run fraction of time spent in each state.

Common Mistakes

Common Mistake

Confusing the transition matrix P with a column-stochastic matrix

Each ROW of the transition matrix sums to 1 (row-stochastic), not each column.

Common Mistake

Assuming stationarity implies convergence from every starting state

Convergence P^n_ij -> pi_j additionally requires aperiodicity; a periodic chain does not converge even if it has a unique stationary distribution.

Common Mistake

Forgetting to sum over ALL intermediate states k in Chapman-Kolmogorov

The Chapman-Kolmogorov equation P^{(m+n)}_ij = sum_k P^{(m)}_ik P^{(n)}_kj must sum over every state k in S.

Quiz

Historical Background

Andrei Markov introduced the concept in 1906 to demonstrate that the law of large numbers could apply to dependent random variables. He analyzed letter frequencies in Pushkin's poetry as an early application. The theory was extended by Kolmogorov in the 1930s to continuous-time processes. By the mid-20th century, Markov chains had become central to statistical mechanics, queuing theory, and eventually to the Google PageRank algorithm and Markov Chain Monte Carlo methods.

1906
Andrei Markov introduces Markov chains to extend the LLN to dependent sequences
Andrei Markov
1931
Kolmogorov develops the general theory of Markov processes
Andrei Kolmogorov
1953
Metropolis et al. introduce Markov Chain Monte Carlo for statistical physics
Nicholas Metropolis
1998
Google's PageRank algorithm is based on the stationary distribution of a Markov chain
Larry Page, Sergey Brin

Summary

A Markov chain satisfies the Markov property: P(Xₙ₊₁|X₀,...,Xₙ) = P(Xₙ₊₁|Xₙ), so dynamics are encoded in the transition matrix P.
The Chapman-Kolmogorov equations give n-step probabilities as the matrix power Pⁿ.
A unique stationary distribution π exists and P^n converges to it when the chain is irreducible and aperiodic.
The mean return time to state i equals 1/πᵢ for positive-recurrent chains.

References

BookDurrett, R. — Probability: Theory and Examples, 4th ed., Chapter 5
BookRoss, S. — Introduction to Probability Models, Chapter 4
WebsiteWikipedia — Markov chain