Markov Chains — Transition Matrices and Stationary Distributions

⚡ Key Takeaways

A Markov chain is a stochastic process whose future evolution depends only on its present state, not its history. Its dynamics are encoded in a transition matrix $P$ whose entries are conditional probabilities, and its long-run behaviour is captured by a stationary distribution $\pi$ satisfying $\pi P = \pi$ . Applies to: queueing theory, PageRank, statistical physics, genetics, MCMC sampling. Core machinery developed by Andrey Markov (1906); convergence theory matured through the 20th century.

💡 The Core Insight

The present screens off the past. Because the future depends on the past only through the current state, the whole evolution reduces to linear algebra: distributions are row vectors, one time step is right-multiplication by $P$ , and equilibrium is a left eigenvector of $P$ with eigenvalue $1$ . Probability theory becomes the spectral theory of a stochastic matrix.

DefinitionMarkov Chain and the Markov Property

Let $S$ be a countable set (the state space). A sequence of $S$ -valued random variables $(X_n)_{n\ge 0}$ is a (time-homogeneous) Markov chain if for all $n\ge 0$ and all states $i_0, \dots, i_{n-1}, i, j$ with positive probability,

1

\quad \mathbb{P}(X_{n+1}=j \mid X_n=i,\, X_{n-1}=i_{n-1},\dots,X_0=i_0) = \mathbb{P}(X_{n+1}=j \mid X_n=i) = P_{ij}.

Derivation hint: this is the definitional axiom; "time-homogeneous" means the right-hand side is independent of $n$ , so a single matrix $P$ suffices. Here $P_{ij}$ is the transition probability from $i$ to $j$ , and $P = (P_{ij})$ is the transition matrix. The initial distribution is the row vector $\mu^{(0)}$ with $\mu^{(0)}_i = \mathbb{P}(X_0 = i)$ .

DefinitionStochastic Matrix

A matrix $P$ is row-stochastic (or simply stochastic) if

2

\quad P_{ij} \ge 0 \quad \text{for all } i,j, \qquad \sum_{j\in S} P_{ij} = 1 \quad \text{for all } i.

Derivation hint: each row is the conditional distribution of $X_{n+1}$ given $X_n=i$ , so it must be a probability vector — nonnegative and summing to one. Every transition matrix is stochastic, and conversely every stochastic matrix with a chosen initial distribution defines a Markov chain.

Definition

n

-Step Transition Matrix and Distribution Evolution

Write $P^{(n)}_{ij} = \mathbb{P}(X_n = j \mid X_0 = i)$ for the $n$ -step transition probability. Then

3

\quad P^{(n)} = P^n, \qquad \mu^{(n)} = \mu^{(0)} P^n,

Derivation hint: iterate the Chapman–Kolmogorov equation $P^{(m+n)} = P^{(m)}P^{(n)}$ ; the row vector $\mu^{(n)}$ of marginal probabilities evolves by right-multiplication, by the law of total probability. where $\mu^{(n)}_j = \mathbb{P}(X_n = j)$ is the distribution at time $n$ .

TheoremChapman–Kolmogorov Equations

For all $m,n\ge 0$ and all states $i,j$ ,

4

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

Derivation hint: condition on the intermediate state $X_m = k$ and use the Markov property to split the path at time $m$ ; this is exactly matrix multiplication $P^{m+n}=P^m P^n$ .

DefinitionStationary Distribution

A probability row vector $\pi = (\pi_i)_{i\in S}$ (so $\pi_i \ge 0$ , $\sum_i \pi_i = 1$ ) is a stationary distribution (or invariant distribution) of $P$ if

5

\quad \pi P = \pi, \quad\text{i.e.}\quad \pi_j = \sum_{i\in S} \pi_i\, P_{ij} \ \text{ for all } j.

Derivation hint: require that if $X_0 \sim \pi$ then $X_1 \sim \pi$ ; by equation [3] this is exactly $\pi P = \pi$ , making $\pi$ a left eigenvector of $P$ for eigenvalue $1$ . If $X_0 \sim \pi$ , then $X_n \sim \pi$ for all $n$ : the chain is in statistical equilibrium.

DefinitionIrreducibility, Period, Recurrence

The chain is irreducible if every state can be reached from every other: for all $i,j$ there exists $n$ with $P^{(n)}_{ij} > 0$ .
The period of state $i$ is $d(i) = \gcd\{n \ge 1 : P^{(n)}_{ii} > 0\}$ . The chain is aperiodic if $d(i)=1$ for all $i$ (in an irreducible chain the period is a common value).
A state is recurrent if $\mathbb{P}(\text{return to } i \mid X_0 = i) = 1$ , and positive recurrent if the mean return time $m_i = \mathbb{E}[T_i \mid X_0=i]$ is finite, where $T_i = \min\{n\ge 1 : X_n = i\}$ .

TheoremExistence, Uniqueness, and Convergence — the Fundamental Theorem

Let $P$ be the transition matrix of an irreducible Markov chain on $S$ . 1. A stationary distribution $\pi$ exists iff the chain is positive recurrent; when it exists it is unique and satisfies $\pi_i > 0$ for all $i$ . 2. (Return-time formula) $\displaystyle \pi_i = \frac{1}{m_i}$ , the reciprocal of the mean return time to $i$ . 3. (Convergence) If in addition the chain is aperiodic, then for every initial distribution $\mu^{(0)}$ ,

6

\quad \lim_{n\to\infty} \mu^{(0)} P^n = \pi, \qquad \text{equivalently} \quad \lim_{n\to\infty} P^{(n)}_{ij} = \pi_j \ \text{ for all } i,j.

Derivation hint: aperiodicity + irreducibility + finite state space makes some power $P^N$ strictly positive; the Perron–Frobenius theorem then forces a simple dominant eigenvalue $1$ with all other eigenvalues strictly inside the unit disk, so $P^n$ converges to the rank-one projection $\mathbf{1}\pi$ .

ProofExistence of

\pi

on a finite irreducible chain

We sketch the finite-state argument, the most important undergraduate case. 1. Stochasticity gives eigenvalue 1. Since each row of $P$ sums to $1$ , the all-ones column vector $\mathbf{1}$ satisfies $P\mathbf{1} = \mathbf{1}$ . Thus $1$ is an eigenvalue of $P$ (a right eigenvector). A matrix and its transpose share eigenvalues, so there exists a left eigenvector $v$ with $vP = v$ . 2. Sign control via Perron–Frobenius. Irreducibility means $P$ (viewed as a nonnegative matrix) is irreducible in the matrix sense. The Perron–Frobenius theorem guarantees that the spectral radius equals $1$ , is a simple eigenvalue, and its left eigenvector $v$ can be taken with all entries strictly positive. 3. Normalisation. Since $v_i>0$ and $\sum_i v_i$ is finite (finite state space), set $\pi_i = v_i / \sum_k v_k$ . Then $\pi$ is a probability vector with $\pi P = \pi$ , establishing existence. $\quad\blacksquare$

∎

ProofUniqueness and the return-time formula

1. Uniqueness. Perron–Frobenius makes eigenvalue $1$ simple, so its eigenspace is one-dimensional; the only probability vector in it is $\pi$ . Hence $\pi$ is unique. 2. Return-time identity. Define the expected number of visits to $i$ between consecutive visits to a fixed reference state. The renewal-reward theorem says the long-run fraction of time in state $i$ equals (expected visits to $i$ per cycle)/(expected cycle length). Choosing the cycle to be a return to $i$ itself gives one visit per cycle of mean length $m_i$ , so the long-run frequency is $1/m_i$ . By the ergodic theorem for Markov chains this frequency equals $\pi_i$ . Hence $\pi_i = 1/m_i$ , and finiteness of $m_i$ (positive recurrence) is exactly the condition for $\pi_i > 0$ . $\quad\blacksquare$

∎

ProofConvergence under aperiodicity (coupling sketch)

1. Construct two coupled copies. Run a chain $X_n$ started from $\mu^{(0)}$ and an independent chain $Y_n$ started from $\pi$ , evolving by the same $P$ . 2. Coupling time. Irreducibility + aperiodicity guarantees the joint chain $(X_n, Y_n)$ is irreducible on $S \times S$ and reaches the diagonal $\{(s,s)\}$ with probability $1$ in finite expected time $\tau$ . 3. Once coupled, stay coupled. After $\tau$ , run $X_n = Y_n$ identically. Since $Y_n \sim \pi$ for all $n$ ,

\big| \mathbb{P}(X_n = j) - \pi_j \big| \le \mathbb{P}(\tau > n) \to 0.

This gives total-variation convergence $\mu^{(0)}P^n \to \pi$ , proving equation [6]. Aperiodicity is essential: without it $\tau$ may be infinite because the two chains never align in phase. $\quad\blacksquare$

∎

mathematician · Andrey Andreyevich Markov | 1856–1922

A student of Pafnuty Chebyshev at St. Petersburg, Markov introduced his chains in 1906 to extend the law of large numbers and the central limit theorem to dependent random variables — refuting the then-common belief that independence was indispensable. In a celebrated 1913 study he applied the method to the sequence of vowels and consonants in Pushkin's Eugene Onegin, arguably the first quantitative analysis of text as a stochastic process. A fierce, principled man, Markov publicly resigned privileges in protest of Tsarist politics. His chains became foundational to twentieth-century probability, information theory, and computation.

🧠 Intuition

Think of a frog hopping among lily pads. The transition matrix $P$ tells you, from whichever pad the frog sits on right now, the odds of each next pad — and crucially the frog has no memory of how it got there. If you place a large cloud of frogs according to distribution $\mu^{(0)}$ and let them all hop once, the new cloud is $\mu^{(0)}P$ ; hop again, $\mu^{(0)}P^2$ . The stationary distribution $\pi$ is the special cloud shape that hops to itself — pour the frogs out in proportion $\pi$ and the population picture never changes, even though every individual frog keeps moving. The convergence theorem says that any starting cloud, after enough hops, relaxes to this same shape $\pi$ — the system forgets its initial condition. And $\pi_i = 1/m_i$ has a beautifully concrete meaning: the busiest pads (high $\pi_i$ ) are exactly the ones the frog returns to fastest.

Figure

Two-state Markov chain and its convergence to the stationary distribution

```svg

```

ExampleTwo-state chain — solving

\pi P = \pi

Given: $S = \{A, B\}$ with

P = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}.

Find the stationary distribution.

Steps. 1. Write $\pi = (\pi_A, \pi_B)$ and solve $\pi P = \pi$ :

\pi_A = 0.7\pi_A + 0.4\pi_B, \qquad \pi_B = 0.3\pi_A + 0.6\pi_B.

2. The first equation gives $0.3\pi_A = 0.4\pi_B \Rightarrow \pi_A = \tfrac{4}{3}\pi_B$ . (The two equations are dependent — expected, since rows of $P-I$ are linearly dependent.) 3. Apply normalisation $\pi_A + \pi_B = 1$ : $\tfrac{4}{3}\pi_B + \pi_B = 1 \Rightarrow \tfrac{7}{3}\pi_B = 1 \Rightarrow \pi_B = \tfrac{3}{7}$ , so $\pi_A = \tfrac{4}{7}$ . 4. Check via return time: $m_A = 1/\pi_A = 7/4 = 1.75$ steps mean return time to $A$ .

\boxed{\pi = \left(\tfrac{4}{7},\ \tfrac{3}{7}\right) \approx (0.571,\ 0.429) \ \text{(dimensionless probabilities)}}

ExampleWeather chain — long-run fractions and a finite-step forecast

Given: States $\{\text{Sunny}, \text{Rainy}\}$ with

P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix},

today is Sunny, i.e. $\mu^{(0)} = (1, 0)$ .

Steps. 1. Two-step forecast: $\mu^{(1)} = \mu^{(0)}P = (0.9, 0.1)$ . Then

\mu^{(2)} = \mu^{(1)}P = (0.9\cdot 0.9 + 0.1\cdot 0.5,\ \ 0.9\cdot 0.1 + 0.1\cdot 0.5) = (0.86,\ 0.14).

So $\mathbb{P}(\text{Sunny in 2 days}) = 0.86$ . 2. Stationary distribution: solve $\pi_S = 0.9\pi_S + 0.5\pi_R$ , giving $0.1\pi_S = 0.5\pi_R$ , so $\pi_S = 5\pi_R$ . Normalise: $6\pi_R = 1$ , $\pi_R = \tfrac16$ , $\pi_S = \tfrac56$ . 3. Interpretation: in the long run roughly $83.3\%$ of days are sunny, independent of today's weather (chain is irreducible and aperiodic — note $P_{SS}>0$ kills periodicity). 4. Mean return time to Rain: $m_R = 1/\pi_R = 6$ days.

\boxed{\pi = \left(\tfrac56,\ \tfrac16\right) \approx (0.833,\ 0.167); \quad \mathbb{P}(\text{sunny in 2 days})=0.86}

⚠️ Common mistake

A stationary distribution is not a fixed state. The chain does not stop at $\pi$ . Individual trajectories keep jumping forever; it is the probability distribution over states that is frozen. Likewise, " $\pi P = \pi$ " is a statement about the row vector $\pi$ (a left eigenvector), not about $P\mathbf{1}=\mathbf{1}$ (the right eigenvector $\mathbf{1}$ , which every stochastic matrix has trivially). Confusing left and right eigenvectors is the single most common error.

⚠️ Common mistake

Existence of $\pi$ does not guarantee convergence. A unique stationary distribution can exist while $\mu^{(0)}P^n$ fails to converge — this happens for periodic chains. Convergence in equation [6] requires aperiodicity in addition to irreducibility and positive recurrence. The time-average (Cesàro mean) $\frac1n\sum_{k<n}\mu^{(0)}P^k$ always converges to $\pi$ for irreducible positive-recurrent chains, but the instantaneous distribution may oscillate forever.

CounterexampleA periodic chain with no convergence

Take $S=\{1,2\}$ and the deterministic swap

P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.

This chain is irreducible and its unique stationary distribution is $\pi = (\tfrac12,\tfrac12)$ (check: $\pi P = \pi$ ). But starting from $\mu^{(0)}=(1,0)$ we get $\mu^{(1)}=(0,1)$ , $\mu^{(2)}=(1,0)$ , $\dots$ — the distribution oscillates with period $2$ and never converges to $(\tfrac12,\tfrac12)$ . The period is $\gcd\{2,4,6,\dots\}=2$ , so the chain is not aperiodic and equation [6] does not apply. The Cesàro average, however, does tend to $(\tfrac12,\tfrac12)$ .

CounterexampleNon-uniqueness when reducibility fails

Take $S=\{1,2,3\}$ with two absorbing states and one transient:

P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \tfrac12 & \tfrac12 & 0 \end{pmatrix}.

This chain is reducible: states $1$ and $2$ are absorbing. Every mixture $\pi = (a, 1-a, 0)$ with $a\in[0,1]$ satisfies $\pi P=\pi$ , so the stationary distribution is far from unique. Irreducibility in the Fundamental Theorem is exactly what rules this out.

connection

Markov chains sit at a crossroads of several theories. The matrix machinery is pure Linear Algebra: stationary distributions are left eigenvectors and convergence rates are governed by the second-largest eigenvalue modulus (the spectral gap). Existence and positivity flow from the Perron–Frobenius Theorem for nonnegative matrices. The convergence proof relies on Coupling of Stochastic Processes and on ergodic ideas shared with Ergodic Theory. The continuous-time analogue replaces $P$ by a generator $Q$ and the equation $\pi P=\pi$ by $\pi Q = 0$ , leading to Continuous-Time Markov Chains and the Kolmogorov Forward and Backward Equations. When the chain satisfies the detailed balance condition $\pi_i P_{ij} = \pi_j P_{ji}$ it is reversible, connecting to Reversible Markov Chains and Detailed Balance and the electrical-network analogy.

🔬 Where this appears

⏳ History

- 1906 — Andrey Markov publishes the first paper on chains of dependent variables, proving a law of large numbers without independence.

- 1907 — Markov extends his results, establishing what we now call irreducibility and the role of the dominant eigenvalue.

- 1912–1913 — Markov analyses letter sequences in Pushkin's Eugene Onegin, the first empirical application.

- 1907–1912 — Georg Frobenius and Oskar Perron develop the spectral theory of nonnegative matrices (Perron–Frobenius theorem), later seen as the algebraic heart of stationary-distribution theory.

- 1931 — Andrey Kolmogorov lays measure-theoretic foundations for Markov processes and derives the forward/backward differential equations for the continuous-time case.

- 1936–1938 — Wolfgang Doeblin introduces coupling and the "Doeblin condition," giving a powerful route to convergence and ergodicity.

- 1953 — Metropolis, Rosenbluth, Rosenbluth, Teller and Teller publish the Metropolis algorithm, launching MCMC in computational physics.

- 1970 — W. K. Hastings generalises it to the Metropolis–Hastings algorithm, opening the door to Bayesian computation.

- 1996–1998 — Sergey Brin and Larry Page apply stationary distributions of the web graph to create PageRank, founding Google.

open-problem

For finite chains the theory is complete, but quantitative and infinite-state questions remain rich. Mixing-time estimation — how many steps until $\|\mu^{(0)}P^n - \pi\|_{TV} < \varepsilon$ — is governed by the spectral gap, yet computing it sharply for high-dimensional chains (e.g. those used in MCMC for hard combinatorial measures) is often open and ties into complexity theory. The cutoff phenomenon, where convergence happens abruptly within a narrow window, is proven only for special families and its general characterisation is unresolved. For countably infinite chains, distinguishing positive recurrence, null recurrence, and transience requires delicate Lyapunov-function or Foster–Lyapunov criteria, and explicit stationary distributions may not exist in closed form. Non-reversible chains, which can mix faster than reversible ones, lack a comprehensive spectral theory — designing optimal non-reversible MCMC samplers is an active research frontier.

Markov Chains — Transition Matrices and Stationary Distributions

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also