Markov Chains

A Markov chain is a stochastic process that moves between the states of a set —tomorrow's weather, a token's position on a board, the next word in a sentence— according to rules of probability. Its defining trait is the Markov property, or «memorylessness»: the probability of the next state depends only on the current state, not on the whole path taken to reach it. The present holds all the information needed to predict the immediate future; once you know where the system is, its past is irrelevant.

The Russian mathematician Andrei Markov (1856-1922) formalized these ideas in 1906, in work that extended the law of large numbers to dependent variables. A century later, the chains that bear his name are a quiet foundation of modern artificial intelligence.

The Markov property and the transition matrix

When the set of states is finite, the chain's dynamics are captured by a transition matrix: each entry gives the probability of moving from one state to another in a single step, and each row sums to one, because from any state something must happen. Multiplying the current distribution of probabilities by this matrix yields the distribution one step later; repeating the operation projects the chain's behavior forward in time. The system's entire memory thus fits into a table of numbers.

The stationary distribution

Many chains settle, over time, into a stationary distribution: a spread of probability that no longer changes when the transition matrix is applied. It is the equilibrium the system converges toward, regardless of where it began. Not every chain reaches one; two conditions are required. Irreducibility demands that every state be reachable from every other; aperiodicity demands that the chain not be trapped in rigid cycles. When both hold, a finite chain converges to a single stationary distribution, whatever its starting point. That result is the deeper reason Markov chains are so useful: they guarantee predictable long-run behavior.

Uses in AI: HMMs, MCMC and PageRank

On this foundation rest some of AI's core tools. Hidden Markov models (HMMs) —made popular in speech recognition through, among others, the work of Lawrence Rabiner— assume a chain whose states are not observed directly but through emitted signals. Markov chain Monte Carlo (MCMC) sampling, with algorithms such as Metropolis-Hastings and Gibbs sampling, deliberately builds a chain whose stationary distribution is the one under study, then lets it run to draw samples; it is the engine behind much of Bayesian statistics. And PageRank, Sergey Brin and Larry Page's original heart of Google, is nothing but a random walk over the web: a page's importance is its probability in the stationary distribution of a surfer hopping from link to link.

The Markov chain should not be confused with the Markov decision process (MDP), its cousin from reinforcement learning: an MDP adds actions and rewards, so that one no longer merely observes a system but decides how to act within it.