The one assumption
A stochastic process is a sequence of random variables indexed by time. A Markov chain is one where the conditional distribution of the next value, given the entire history, collapses to a dependence on the most recent value alone.
What it buys
- Tractability. A joint distribution over T steps that would need exponentially many parameters factorizes into T copies of one small matrix.
- Simulation. Generating a path needs only the current state, so you can run one forever in constant memory.
- Long-run answers. Questions about behaviour after infinite time reduce to linear algebra on a finite matrix.
- Composability. Add actions and you have an MDP. Hide the states and you have an HMM. Both inherit the tractability.
What it costs
Real systems often remember. How long you've been in a state usually matters; a machine that has run for eight hours is not the same as one that just started, even if both are labelled "working".
Everything in one table
For a finite state space, the whole chain is a square matrix. Entry P[i][j] is the probability of moving to state j given that you're in state i.
Properties
- P[i][j] ≥ 0
- Probabilities, so non-negative.
- rows sum to 1
- From any state you must go somewhere, possibly back to where you were. Called row-stochastic.
- columns don't
- A common early confusion. Only the rows are constrained.
- self-loops
- The diagonal is "stay put", and it's usually the largest entry in slow-moving systems.
Evolving a distribution
With π as a row vector multiplied on the left. Each new entry is a weighted average of where you might have been, weighted by the chance of arriving from there.
Powers give multi-step behaviour
The (i,j) entry of Pn is the probability of being in j exactly n steps after starting in i. That's a genuinely useful fact — questions about "where will it be in ten steps" are answered by matrix multiplication, not simulation.
Which says nothing more than: to get somewhere in m+n steps, be somewhere after m and continue. The Markov property is what makes that decomposition valid.
The vocabulary that decides everything
Whether a chain has a unique long-run distribution — and whether it actually converges to it — comes down to two structural properties. These are the conditions the hero's four presets are testing.
| Term | Meaning | Why it matters |
|---|---|---|
| accessible | j is reachable from i in some number of steps | The basic connectivity relation |
| communicating | Each is accessible from the other | Partitions the states into classes |
| irreducible | Every state reaches every other — one class | Required for a unique stationary distribution |
| recurrent | You return with probability 1 | Guaranteed for all states of a finite irreducible chain |
| transient | Positive chance of never returning | These get zero stationary probability |
| absorbing | Once entered, never left — P[i][i] = 1 | Breaks irreducibility. All mass ends up here |
| period | GCD of all return-time lengths | Period 1 means aperiodic |
| aperiodic | Returns aren't locked to a rhythm | Required for convergence, not for existence |
| ergodic | Irreducible and aperiodic | The good case. Everything works |
The distribution that doesn't move
A stationary distribution is a probability vector that the chain leaves unchanged. Push it through one step and you get it back.
As linear algebra
π is a left eigenvector of P with eigenvalue 1, normalized to sum to one. Every stochastic matrix has such an eigenvalue — the all-ones column vector is the corresponding right eigenvector, since rows sum to 1.
As balance
Probability flowing into each state exactly equals probability flowing out. The system is in equilibrium — not static, since individual walkers keep moving, but macroscopically unchanging.
As time spent
πi is the long-run fraction of time a single walker spends in state i. It's also the reciprocal of the mean return time to i — a state you visit every ten steps on average carries 0.1 of the mass.
The fundamental theorem
For a finite chain that is irreducible and aperiodic:
- A stationary distribution exists.
- It is unique.
- πt converges to it from any starting distribution.
- Every πi is strictly positive.
Drop irreducibility and uniqueness goes. Drop aperiodicity and convergence goes, though a unique stationary distribution may still exist.
Stationary versus limiting
These are different and the periodic preset shows why. A deterministic four-cycle has a perfectly good stationary distribution — uniform, ¼ each. Start there and you stay there forever.
But start all the mass in one state and it will march around the cycle indefinitely, never converging. The stationary distribution exists; the chain never reaches it. What does converge is the time-average, which is why period is a problem for simulation but not for equilibrium.
# three ways to find it, all agreeing import numpy as np P = np.array([[0.30, 0.60, 0.08, 0.02], [0.15, 0.35, 0.48, 0.02], [0.10, 0.25, 0.60, 0.05], [0.40, 0.30, 0.10, 0.20]]) # 1 — power iteration: just run it forward pi = np.ones(4) / 4 for _ in range(1000): pi = pi @ P # 2 — eigenvector: left eigenvector of P for eigenvalue 1 vals, vecs = np.linalg.eig(P.T) v = np.real(vecs[:, np.argmin(np.abs(vals - 1))]) pi_eig = v / v.sum() # 3 — solve the linear system directly # (P^T - I)pi = 0, with the normalization row appended A = np.vstack([P.T - np.eye(4), np.ones(4)]) b = np.array([0, 0, 0, 0, 1]) pi_solve = np.linalg.lstsq(A, b, rcond=None)[0]
Power iteration is the one to reach for on large sparse chains — it needs only matrix-vector products, never a factorization. That's exactly how PageRank is computed over billions of pages.
How fast does it forget?
Convergence is guaranteed for an ergodic chain, but the rate varies enormously and it's the rate that decides whether a method is practical.
Total variation distance
The standard measure of how far the current distribution is from equilibrium. It runs from 0 to 1 and it's the number displayed in the hero. Mixing time is how many steps it takes to get that below some small threshold.
The spectral gap
Every stochastic matrix has λ1 = 1. The second-largest eigenvalue in absolute value controls convergence: the distance to stationarity decays roughly like |λ₂|ᵗ. A large gap means fast mixing. A gap near zero means a chain that crawls — and a λ2 of exactly −1 is what periodicity looks like in the spectrum.
Bottlenecks
Two well-connected regions joined by a narrow bridge. Fine locally, catastrophic globally. Formalized by the conductance of the graph.
Near-periodicity
Not periodic, but almost. The distribution oscillates while slowly damping, and naive convergence checks read the oscillation as noise.
Dimension
Random-walk proposals mix badly as dimension grows, which is the entire reason gradient-based samplers like HMC exist.
One walker, watched long enough
Everything so far tracked a distribution — probability mass spread across states. The ergodic theorem says you can get the same answer from a single walker: the fraction of time it spends in each state converges to the stationary distribution. Run one and watch.
Designing a chain backwards
So far the chain came first and the stationary distribution was whatever fell out. MCMC inverts this: you know the distribution you want and need a chain that has it. Detailed balance is the tool that makes the inversion easy.
The flow of probability from i to j exactly matches the flow back. Sum over i and stationarity follows immediately — so detailed balance is a sufficient condition, and a much easier one to arrange than solving πP = π directly.
Continuous states, continuous time
Continuous state space
The matrix becomes a transition kernel K(x, dy), sums become integrals, and stationarity reads ∫ π(x) K(x, A) dx = π(A). Irreducibility and aperiodicity get technical replacements (Harris recurrence), but the shape of the theory survives.
This is the setting every real MCMC sampler lives in — the states are parameter vectors in ℝᵈ, not four labelled boxes.
Continuous time
Transitions happen at random moments rather than on a clock. The generator matrix Q replaces P, its rows sum to zero, and P(t) = e^{Qt}. Stationarity becomes πQ = 0.
Poisson process
Counting events with exponential gaps. Arrivals at a queue, photons at a detector, failures in a fleet.
Birth–death chains
Transitions only to neighbouring states. Queue lengths, population sizes, inventory levels.
Random walks
On a line, a lattice, or a graph. The unbounded ones are recurrent in one and two dimensions but transient in three — a famous and genuinely surprising result.
When you can't see the state
A hidden Markov model puts a Markov chain underneath and lets you observe only a noisy signal emitted from each state. The chain is real; the states are not directly measurable.
| Question | Algorithm | What it computes |
|---|---|---|
| How likely is this sequence? | Forward | P(observations) by summing over every possible hidden path |
| What state am I in now? | Forward (filtering) | P(state at t | observations up to t) — the online case |
| What state was I in then? | Forward–backward | P(state at t | all observations) — smoothing, with hindsight |
| What was the most likely path? | Viterbi | The single best state sequence, by dynamic programming |
| What are the parameters? | Baum–Welch | EM for the transition and emission matrices from unlabelled data |
Where this actually gets used
| Where | States | What the stationary distribution means |
|---|---|---|
| MCMC | Parameter values | The posterior itself. The chain is engineered to have it |
| PageRank | Web pages | Long-run fraction of time a random surfer spends on each page — the ranking |
| MDPs / RL | Environment states | State visitation frequency under a policy. Central to policy gradient theory |
| n-gram language models | Recent words | Unigram frequencies. The chain is the model |
| Queueing theory | Number waiting | Long-run queue length distribution. Capacity planning |
| Credit ratings | Rating grades | Long-run portfolio composition, and default probabilities via absorption |
| Reliability | Working / degraded / failed | Steady-state availability. Failure is often an absorbing state |
| Genetics | Alleles, sequence motifs | Equilibrium frequencies. HMMs for gene finding and alignment |
| Speech & handwriting | Phonemes, strokes | HMMs dominated both fields before deep learning arrived |
| Customer lifecycle | Active / lapsed / churned | Steady-state mix, and expected time to churn via absorption |
PageRank, in one sentence
Model a surfer who follows a random outbound link at each step. The stationary distribution of that chain is the ranking — pages are important if important pages point at them, which is circular in exactly the way an eigenvector resolves.
The clever part is the fix. A raw web graph is neither irreducible nor aperiodic — dangling pages and disconnected regions break both. So with probability 0.15 the surfer teleports to a page chosen at random. That single modification makes every state reachable from every other, guarantees a unique stationary distribution, and sets the mixing rate. Fifty years of Markov theory, applied as one damping constant.
The assumption is usually wrong. Sometimes that's fine.
Repairs, in order of cost
- enlarge state
- Fold the needed history in. Exact, and the state space grows exponentially.
- higher order
- Condition on the last k states. Same trade, stated differently.
- semi-Markov
- Let holding times have arbitrary distributions rather than geometric.
- hidden states
- An HMM's latent variable can carry information the observations don't.
- learned state
- An RNN or transformer hidden vector as a soft, continuous, learned summary of history. Strictly more general, entirely uninterpretable.
Drills
| # | Do this | You'll know it when |
|---|---|---|
| 1 | Write a 3-state transition matrix by hand and evolve a distribution five steps on paper | Row-stochastic and left-multiplication are automatic |
| 2 | Find the stationary distribution three ways — power iteration, eigenvector, linear solve | All three agree, and you know when to use each |
| 3 | Build a periodic chain and plot the distribution over time | You can explain why a stationary distribution exists but is never reached |
| 4 | Add one small self-loop to that chain and re-run | You watch aperiodicity restore convergence |
| 5 | Simulate a single walker and plot visit frequencies against π | The ergodic theorem is something you've seen, not read |
| 6 | Compute the second eigenvalue for a fast and a slow chain | The spectral gap predicts what you observe |
| 7 | Build an absorbing chain and compute expected time to absorption | Fundamental matrix methods make sense |
| 8 | Verify detailed balance for a chain you constructed, then for one you didn't | You see that stationarity is the weaker condition |
| 9 | Implement PageRank on a twenty-node graph, with and without damping | You can point at what teleportation actually fixes |
| 10 | Fit a bigram model on text, then find its stationary distribution | It's the unigram frequency table, and you know why |
The one-paragraph summary
A Markov chain is a stochastic process whose next state depends only on the current one, which for a finite state space means the whole thing is a row-stochastic transition matrix, distributions evolve by left-multiplication, and n-step behaviour is a matrix power. A stationary distribution satisfies πP = π — a left eigenvector for eigenvalue 1 — and can be read as an equilibrium of probability flow or as the long-run fraction of time spent in each state. If the chain is irreducible it has a unique one, and if it is also aperiodic then any starting distribution converges to it, at a rate governed by the second-largest eigenvalue. The ergodic theorem then says a single walker's visit frequencies converge to the same distribution, which is the entire justification for MCMC; detailed balance is the sufficient condition that lets you construct a chain with a chosen stationary distribution, and is where Metropolis–Hastings comes from. The memorylessness assumption is almost always false in detail, and the standard repair is to enlarge the state until it becomes true — which is a statement about your model, not about the world.