Markov chain

The process whose future depends on its present and not on the path that got it there. Given where it is now, how it arrived carries no further information — which is a strong assumption, and the reason the theory is as complete as it is.

The discrete theory

wu-introduction-stochastic-processes spends thirteen of twenty-four lectures here, and the sequence is the standard one: finite chains and their transition probabilities, stationary distributions, time-reversal, then mixing times — how long until the chain forgets where it started — with stationary times and lower-bound techniques given five lectures of their own. Then random walks on networks, hitting times, and countable state spaces, where the finite-case arguments stop working.

Continuous time arrives at the end: the infinitesimal generator, irreducibility and recurrence, and stationary distributions again. The generator is the derivative of the transition operator at time zero, and it is what connects this discrete-flavoured subject to the analytic machinery on brownian-motion — a Brownian motion is a Markov process too, and its generator is the Laplacian that produces the heat equation.

stirzaker-elementary-probability carries the same material at undergraduate altitude in its chapter 9: transition probabilities, first-passage times, stationary distributions, long-run behaviour.

What the courses leave out (added 2026-09-05). dynkin-yushkevich-markov-processes starts in the same place — a symmetric random walk on a lattice — and goes somewhere none of the courses do. Its first chapter builds harmonic functions, potential, excessive functions and capacity for that walk, all borrowed from classical analysis, and then uses them to answer a purely probabilistic question: whether a given set is visited infinitely often. Its third chapter turns the same excessive functions into a theory of optimal stopping, and its fourth reads boundary conditions off the paths of a birth-and-death process. The Martin boundary for a denumerable chain is in that book's problem sets. None of this appears in the three courses, which is worth noting because it is not advanced material bolted on top — it is a different set of questions to ask about the same object.

Why linear algebra is the prerequisite

A finite Markov chain is a matrix. Transition probabilities form a stochastic matrix, evolving the distribution is multiplication by it, and the stationary distribution is a left eigenvector with eigenvalue 1. That is why wu-introduction-stochastic-processes asks for conditional expectation and matrix operations and nothing else — the whole of the finite theory is linear-algebra with a probabilistic reading.

This is the clearest instance in the corpus of a subject here being consumed as a tool by another subject here, rather than by an applied spoke.

The hub does not actually use it yet

Worth stating, because the opposite is the obvious guess. A grep across the corpus on the day this page was written found no applied spoke using Markov chains by name. ../machine-learning-wiki's monte-carlo-methods does not mention them, so the Markov-chain Monte Carlo bridge — sampling by constructing a chain whose stationary distribution is the target — is absent from both ends. ../quant-trading-wiki's market-regime-analysis is the nearest miss and is not this: its regimes are labelled by hand in one source and fitted with Gaussian mixtures in another, with no transition structure and no memorylessness assumption anywhere.

So this page currently documents a body of theory the hub's applied spokes have not reached, rather than one they lean on. That is a gap in them, not in it.

Related

stochastic-processes · martingale · brownian-motion · probability-theory · linear-algebra · wu-introduction-stochastic-processes · stirzaker-elementary-probability · lawler-stochastic-calculus · mathematics · synthesis