Markov Chains — Transition Matrices and Stationary Distributions

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.

A discrete-time Markov chain on a finite or countable state space $S$ is a sequence of random variables $(X_0,X_1,X_2,\dots )$ in which the conditional distribution of $X_{n+1}$ given the entire past depends only on $X_n$ — the memoryless or Markov property. The one-step dynamics are summarised by a transition matrix $P$ with $P_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$, a row-stochastic matrix. The central questions of the theory are: how does the distribution evolve (answer: by repeated matrix multiplication), and does it settle down to an equilibrium (answer: under irreducibility and aperiodicity, yes — to the unique stationary distribution $\pi$). The surprising fact is that the long-run fraction of time spent in a state equals $\pi$ regardless of the starting state, and equals the reciprocal of the mean return time. This single framework unifies random walks, gambling problems, web search, and the entire engine of modern Bayesian computation.

The Core Insight

Formal Statement

Markov 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,

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 }_i^{(0)}=\mathbb{P}(X_0=i)$.

Stochastic Matrix

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

Every transition matrix is stochastic, and conversely every stochastic matrix with a chosen initial distribution defines a Markov chain.

$n$-Step Transition Matrix and Distribution Evolution

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

where ${\mu }_j^{(n)}=\mathbb{P}(X_n=j)$ is the distribution at time $n$.

Chapman–Kolmogorov Equations

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

Stationary 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

If $X_0\sim \pi$, then $X_n\sim \pi$ for all $n$: the chain is in statistical equilibrium.

Irreducibility, Period, Recurrence

• The chain is irreducible if every state can be reached from every other: for all $i,j$ there exists $n$ with $P_{ij}^{(n)}>0$.
• The period of state $i$ is $d(i)=\gcd \{n\ge 1:P_{ii}^{(n)}>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\}$.

Existence, 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) ${\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)}$,

Why It Holds / Derivation

Existence 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 $1$ satisfies $P1=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$.

1. 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.

1. 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. $■$

Uniqueness 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.

1. 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$. $■$

Convergence 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$.

1. 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$.

1. Once coupled, stay coupled. After $\tau$, run $X_n=Y_n$ identically. Since $Y_n\sim \pi$ for all $n$,

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.

Building 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.

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

<svg viewBox="0 0 640 360" xmlns="http://www.w3.org/2000/svg">
<rect width="640" height="360" fill="#0a0e17"/>
<text x="20" y="30" fill="#e2e8f0" font-family="sans-serif" font-size="16">Two-state chain: P=[[0.7,0.3],[0.4,0.6]]</text>
<!-- states -->
<circle cx="160" cy="120" r="34" fill="none" stroke="#94a3b8" stroke-width="2"/>
<text x="150" y="126" fill="#e2e8f0" font-family="sans-serif" font-size="20">A</text>
<circle cx="360" cy="120" r="34" fill="none" stroke="#94a3b8" stroke-width="2"/>
<text x="350" y="126" fill="#e2e8f0" font-family="sans-serif" font-size="20">B</text>
<!-- A to B -->
<path d="M194 108 Q260 80 326 108" fill="none" stroke="#94a3b8" stroke-width="2" marker-end="url(#ar)"/>
<text x="250" y="78" fill="#e2e8f0" font-family="sans-serif" font-size="13">0.3</text>
<!-- B to A -->
<path d="M326 132 Q260 160 194 132" fill="none" stroke="#94a3b8" stroke-width="2" marker-end="url(#ar)"/>
<text x="250" y="168" fill="#e2e8f0" font-family="sans-serif" font-size="13">0.4</text>
<!-- self loops -->
<path d="M132 100 Q100 60 150 88" fill="none" stroke="#94a3b8" stroke-width="2" marker-end="url(#ar)"/>
<text x="92" y="70" fill="#e2e8f0" font-family="sans-serif" font-size="13">0.7</text>
<path d="M388 100 Q420 60 370 88" fill="none" stroke="#94a3b8" stroke-width="2" marker-end="url(#ar)"/>
<text x="418" y="70" fill="#e2e8f0" font-family="sans-serif" font-size="13">0.6</text>
<!-- convergence plot -->
<line x1="120" y1="320" x2="560" y2="320" stroke="#94a3b8" stroke-width="1.5"/>
<line x1="120" y1="320" x2="120" y2="210" stroke="#94a3b8" stroke-width="1.5"/>
<text x="540" y="338" fill="#94a3b8" font-family="sans-serif" font-size="12">n</text>
<text x="70" y="216" fill="#94a3b8" font-family="sans-serif" font-size="12">P(A)</text>
<!-- stationary line pi_A = 4/7 ~ 0.571 -->
<line x1="120" y1="272" x2="560" y2="272" stroke="#94a3b8" stroke-width="1" stroke-dasharray="5 4"/>
<text x="565" y="276" fill="#94a3b8" font-family="sans-serif" font-size="11">&#960;&#8320;=0.571</text>
<!-- curve from P(A)=1 converging -->
<path d="M120 213 L175 245 L230 262 L285 268 L340 271 L395 272 L450 272 L560 272" fill="none" stroke="#d4a853" stroke-width="2.5"/>
<text x="180" y="232" fill="#d4a853" font-family="sans-serif" font-size="12">start X&#8320;=A</text>
<defs>
<marker id="ar" markerWidth="8" markerHeight="8" refX="6" refY="3" orient="auto">
<path d="M0,0 L6,3 L0,6 Z" fill="#94a3b8"/>
</marker>
</defs>
</svg>

Worked Examples

Two-state chain — solving $\pi P = \pi$

1. Write $\pi =({\pi }_A,{\pi }_B)$ and solve $\pi P=\pi$:

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

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

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

1. 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=\frac{1}{6}$, ${\pi }_S=\frac{5}{6}$.
2. 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).
3. Mean return time to Rain: $m_R=1/{\pi }_R=6$ days.

Common Misconceptions

A periodic chain with no convergence

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

Non-uniqueness when reducibility fails

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

Connections

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.

Real-World Applications

1. Google PageRank. The web is a Markov chain whose states are pages and transitions are hyperlinks (plus a "teleport" term ensuring irreducibility/aperiodicity). The stationary distribution $\pi$ is the PageRank vector — pages with high ${\pi }_i$ are visited often by a random surfer and ranked higher.
2. Markov Chain Monte Carlo (MCMC). Algorithms like Metropolis–Hastings and the Gibbs sampler construct a chain whose stationary distribution is a desired (often intractable) target $\pi$; running it long enough produces samples from $\pi$. This is the backbone of Bayesian statistics and statistical physics simulation.
3. Queueing theory. The number of customers in an M/M/1 queue is a birth–death Markov chain; its stationary distribution gives steady-state queue length, waiting time, and server utilisation $\rho$.
4. Population genetics. The Wright–Fisher and Moran models treat allele frequencies as Markov chains; absorption probabilities give fixation probabilities of genes.
5. Speech and language. Hidden Markov Models underlie speech recognition, part-of-speech tagging, and bioinformatics gene-finding; Markov's own vowel/consonant study was the prototype.
6. Reliability engineering. Systems cycling through "working/degraded/failed" states are modelled as Markov chains; $\pi$ yields long-run availability.
7. Card shuffling. The riffle shuffle is a Markov chain on the symmetric group; the "seven shuffles" result of Bayer–Diaconis is a cutoff-phenomenon statement about its convergence to the uniform stationary distribution.

Historical Development

• 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.

Subtleties & Limits

For finite chains the theory is complete, but quantitative and infinite-state questions remain rich. Mixing-time estimation — how many steps until $\Vert {\mu }^{(0)}{P}^n-\pi {\Vert }_{TV}<\epsilon$ — 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.

See Also