Markov Chains
Markov chains explained: memoryless processes, transition matrices, stationary distributions, and uses from PageRank to weather models and text generation.
A Markov chain is a random process that moves between states where the next state depends only on the current state, not the history — the Markov or memoryless property. Described by a transition matrix of probabilities, Markov chains model weather, stock prices, web browsing, and text, and underpin algorithms like PageRank.
Transition matrices and the memoryless property
A Markov chain is defined by a set of states and transition probabilities: from state i the chain moves to state j with probability P(i to j), collected into a transition matrix whose rows sum to one. The memoryless property means the future depends only on the present — knowing how the chain arrived adds nothing to the prediction. Weather models are the textbook example:
| From / To | Sunny | Rainy |
|---|---|---|
| Sunny | 0.8 | 0.2 |
| Rainy | 0.4 | 0.6 |
Board games, queuing systems, and DNA sequences follow the same mathematics. Conditioning on the present to predict the future is the same instinct behind Bayes' theorem, applied to sequences rather than single events.
Stationary distributions and long-run behavior
Run a chain long enough and it often settles into a stationary distribution: a probability vector unchanged by further transitions, describing the long-run fraction of time spent in each state. Ergodic chains — those that are irreducible and aperiodic — converge to a unique stationary distribution from any starting state, which is why the concept powers ranking and sampling algorithms. Markov chain Monte Carlo methods exploit this in reverse: design a chain whose stationary distribution is the distribution you want to sample from, then simulate the chain. Metropolis-Hastings and Gibbs sampling built entire fields of Bayesian statistics on this trick, turning integration problems into simulation problems. Convergence speed depends on the chain's mixing time: well-connected chains forget their starting state in a few steps, while chains with bottlenecks linger, and diagnosing slow mixing is a central practical skill in applied MCMC work. Running multiple chains from dispersed starts and comparing their trajectories is the standard check that mixing has actually occurred.
Applications from PageRank to reinforcement learning
PageRank modeled web surfers as a Markov chain over pages, with the stationary distribution measuring page importance — links as votes, plus random teleportation guaranteeing ergodicity. Hidden Markov models extend chains with noisy observations, decoding speech, gene sequences, and part-of-speech tags from indirect evidence. In reinforcement learning, Markov decision processes add actions and rewards to the framework, and agents learn policies maximizing long-run return. Strategic settings layer choice onto chance: game theory studies equilibria when transition probabilities depend on competing players rather than fixed dice.
Tags
markov chains probability statistics stochastic processes