Markov Chains

A Markov chain is a stochastic process with no memory: the future depends on the past only through the present state. That single simplifying assumption is strong enough to model regime switching, credit-rating migration, order-book dynamics, and the random walks underlying option pricing, yet weak enough to remain analytically tractable, because the entire dynamics collapse into a matrix. Understanding chains means understanding how a matrix's spectrum governs the long-run behaviour of a random system, which is why this topic sits at the meeting point of probability and Linear Algebra for Quants.

The Markov property and the transition matrix

A discrete-time process $\{X_n\}$ on a finite (or countable) state space $S$ is a Markov chain if $\mathbb{P}(X_{n+1} = j \mid X_n = i, X_{n-1}, \dots, X_0) = \mathbb{P}(X_{n+1} = j \mid X_n = i) = P_{ij}.$ Conditioning on the whole history is the same as conditioning on the current state alone. The numbers $P_{ij}$ form the transition matrix $P$, a row-stochastic matrix: $P_{ij} \ge 0$ and each row sums to $1$ (from some state you go somewhere with probability 1). Represent a distribution over states as a row vector $\pi$; then one step evolves it by right-multiplication, $\pi_{n+1} = \pi_n P$, and $n$ steps by $\pi_n = \pi_0 P^n, \qquad (P^n)_{ij} = \mathbb{P}(X_n = j \mid X_0 = i).$ The Chapman–Kolmogorov equation $P^{m+n} = P^m P^n$ is just matrix multiplication, and it is the reason the entire theory is linear-algebraic: multi-step probabilities are matrix powers.

The stationary distribution

A distribution $\pi$ is stationary if it is unchanged by a step: $\pi P = \pi, \qquad \sum_i \pi_i = 1, \quad \pi_i \ge 0.$ Read as an Eigenvalues & Eigenvectors equation, $\pi$ is a left eigenvector of $P$ with eigenvalue $1$. Every stochastic matrix has $1$ as an eigenvalue (the all-ones vector is a right eigenvector since rows sum to 1), and the Perron–Frobenius theorem guarantees a corresponding non-negative left eigenvector that, normalised, is a genuine probability distribution. The stationary distribution is the long-run fraction of time spent in each state and the equilibrium the chain relaxes toward.

Classification, ergodicity, and convergence

Whether $\pi$ is unique and whether the chain converges to it depend on structural properties:

• Irreducible: every state reaches every other state (the chain is one communicating class). This gives a unique stationary distribution.
• Aperiodic: the chain is not trapped in deterministic cycles (gcd of return times is 1). This ensures $P^n$ actually converges rather than oscillating.
• Positive recurrent: expected return time to each state is finite (automatic for finite irreducible chains).

An irreducible, aperiodic, positive-recurrent chain is ergodic, and then the fundamental convergence theorem holds: $P^n_{ij} \to \pi_j \quad \text{for all } i,\qquad \text{i.e.}\quad \pi_0 P^n \to \pi \ \text{regardless of } \pi_0.$ The chain forgets its start. The ergodic theorem upgrades this to time averages: for any function $f$, $\frac{1}{n}\sum_{k=1}^n f(X_k) \xrightarrow{\text{a.s.}} \sum_i \pi_i f(i) = \mathbb{E}_\pi[f].$ This is the The Law of Large Numbers for dependent data, a single long trajectory estimates equilibrium expectations, which is exactly what makes Markov Chain Monte Carlo work: engineer a chain whose stationary distribution is your target, run it long, and average. The rate of convergence to $\pi$ is governed by the second-largest eigenvalue modulus $|\lambda_2|$ (the spectral gap $1 - |\lambda_2|$): mixing time scales like $1/(1-|\lambda_2|)$, so the spectrum literally sets how fast the chain equilibrates.

Worked example, a two-state regime model

Model markets as "calm" (state 1) and "stressed" (state 2), with $P = \begin{pmatrix} 0.95 & 0.05 \\ 0.30 & 0.70 \end{pmatrix}.$ Calm persists (95%), stress mean-reverts (70% chance of exiting). Solve $\pi P = \pi$ with $\pi_1 + \pi_2 = 1$. The balance equation is $\pi_1 \cdot 0.05 = \pi_2 \cdot 0.30$ (flow out of calm equals flow in), giving $\pi_1 = 6\pi_2$, so $\pi = \left(\tfrac{6}{7},\ \tfrac{1}{7}\right) \approx (0.857,\ 0.143).$ The market is stressed about 14% of the time in the long run. The expected duration of a stress spell is $1/(1-0.70) = 3.33$ periods (a geometric first-passage result). This tiny model is the skeleton of regime-switching volatility models and Regime Detection; the same eigenvector calculation scales to credit-migration matrices with dozens of rating states.

Hitting times and first passage

Many quant questions, time to default, gambler's ruin, barrier options, are hitting-time problems. Let $h_i$ be the expected number of steps to reach a target set $A$ starting from state $i$. Conditioning on the first step gives a linear system: $h_i = 0 \text{ for } i \in A, \qquad h_i = 1 + \sum_{j} P_{ij}\, h_j \text{ for } i \notin A.$ Similarly, absorption probabilities $u_i = \mathbb{P}(\text{hit } A \text{ before } B \mid X_0 = i)$ solve the harmonic system $u_i = \sum_j P_{ij} u_j$ with boundary values $1$ on $A$, $0$ on $B$. Gambler's ruin is the canonical instance: a symmetric walk on $\{0,\dots,N\}$ with absorbing ends gives ruin probability $u_i = 1 - i/N$, linear in wealth, and expected duration $i(N-i)$. These first-step decompositions are the discrete cousins of the PDEs that price barrier and American options, and the harmonic-function structure links directly to Martingales.

Failure modes and subtleties

• The Markov property is an assumption, often false. Real returns have longer memory (volatility clustering, momentum); forcing a first-order chain loses it. Remedy: enlarge the state to include recent history (a $k$-th order chain is Markov on tuples), at the cost of exponentially more states.
• Reducible or periodic chains don't converge to a unique $\pi$. Multiple communicating classes give multiple stationary distributions; periodicity makes $P^n$ oscillate forever. Check irreducibility and aperiodicity before trusting equilibrium.
• Slow mixing hides in a small spectral gap. A chain can be ergodic in theory but take astronomically long to mix if $|\lambda_2| \approx 1$ (near-decomposable, "sticky" states). MCMC that hasn't mixed gives confidently biased estimates.
• Non-stationary transition matrices. Estimated $P$ from data assumes the dynamics are time-homogeneous; regime parameters drift, so a migration matrix fit in calm markets misprices stress.
• Continuous-time subtlety. The continuous analogue uses a generator matrix $Q$ (rows sum to $0$) with $P(t) = e^{Qt}$; discretising a continuous chain naively can produce invalid transition matrices.

In interviews

Stationary-distribution questions are staples: set up and solve $\pi P = \pi$ for a small chain, and recognise it as a left-eigenvector problem. Gambler's ruin is asked constantly, know both the ruin probability ($1 - i/N$ symmetric, and the geometric-ratio formula for biased walks) and the expected duration. Expect first-step-analysis prompts ("expected number of coin flips to see HH vs. HT") which are hitting-time systems in disguise and famously have different answers. A deeper probe is "when is the stationary distribution unique?", irreducibility, and "what controls how fast the chain reaches it?", the spectral gap, tying back to Eigenvalues & Eigenvectors. Strong candidates connect the ergodic theorem to why MCMC and long-run backtest averages are meaningful for dependent data.