Markov chain

A Markov chain is a stochastic process in which the probability of the next state depends only on the current state and not on the sequence of states that came before it. This defining feature, the conditional independence of the future from the past given the present, is called the Markov property, and it is what makes the family analytically tractable ^[1][3]. Formally, a discrete-time Markov chain is a sequence of random variables $X_0, X_1, X_2, \ldots$ taking values in a state space S such that $P(X_{n+1} = x \mid X_0, X_1, \ldots, X_n) = P(X_{n+1} = x \mid X_n)$ for every n and every x. A Markov chain is the simplest non-trivial generalisation of an independent and identically distributed sequence: it allows memory of length one while preserving most of the analytic structure of independent sequences. As J. R. Norris opens his standard graduate text, "Markov chains are the simplest mathematical models for random phenomena evolving in time" ^[3].

Markov chains were introduced by the Russian mathematician Andrey Markov in a 1906 paper that extended the law of large numbers to sequences of dependent random variables ^[1][24]. They are the foundation for hidden Markov models, Markov decision processes, Markov chain Monte Carlo (MCMC) sampling, the Google PageRank algorithm, n-gram language models, queuing theory, population genetics, and a long list of recent constructions including diffusion-based generative models ^{[9][11][16][17]}. Almost every problem in reinforcement learning is, at heart, a problem about a Markov chain or its decision-making cousin, the Markov decision process ^[8].

ELI5: what is a Markov chain?

Imagine a board game where the only thing that matters for your next move is the square you are standing on right now, not how you got there. A Markov chain is exactly that kind of "memoryless" rule: the future depends only on where you are, never on the path you took to arrive. Weather that is just "sunny or rainy, and tomorrow depends only on today" is a Markov chain. So is a frog hopping between lily pads at random, or the way a phone keyboard guesses your next word from the current one. Because the rule is so simple, mathematicians can predict the long-run behaviour: what fraction of days are sunny, how long until the frog visits every pad, and where things settle down over time.

When were Markov chains invented?

Andrey Markov (1856 to 1922) studied under Pafnuty Chebyshev at Saint Petersburg University and worked on probability and number theory. Chebyshev had proved a law of large numbers for independent random variables; Markov set out to show that the future need only be conditionally independent of the past given the present. The 1906 paper "Distribution of the law of large numbers for quantities depending on one another" established this generalisation and is the founding document of Markov-chain theory ^[1][24].

Markov was responding in part to a public dispute with Pavel Nekrasov, a Moscow University mathematician who had argued on theological grounds that the law of large numbers required statistical independence and therefore proved the existence of free will. Markov constructed his chains specifically to refute this: here was a class of dependent processes for which the law of large numbers still held ^[24].

In 1913 Markov gave a now-famous application of his theory at an address to the Imperial Academy of Sciences in Saint Petersburg. He took the first 20,000 letters of Alexander Pushkin's verse novel Eugene Onegin, stripped out the spaces and punctuation, and classified each letter as a vowel or a consonant. About 43 percent of the letters were vowels and 57 percent consonants. Counting transitions, he found 1,104 vowel-to-vowel pairs, 3,827 consonant-to-consonant pairs, and 15,069 mixed pairs ^[2][24]. The transition counts departed clearly from what one would expect under independence, which Markov used to estimate the parameters of a two-state chain on the alphabet. The Eugene Onegin study was one of the first probabilistic analyses of natural language. Claude Shannon drew directly on Markov's framework in his 1948 paper A Mathematical Theory of Communication, generating English-like text from n-gram statistics ^[21].

Andrey Kolmogorov introduced the continuous-time framework in 1931; Sydney Chapman had independently derived the equation bearing both their names in 1928 ^[23]. Postwar work generalised the theory further: Kemeny and Snell's 1960 monograph Finite Markov Chains gave the modern textbook treatment of finite chains ^[4]; Doob's Stochastic Processes (1953) embedded Markov processes in the broader theory of measurable processes ^[22]; texts by Norris (1997), Grimmett and Stirzaker (2001), and Levin, Peres, and Wilmer (2008) became standard graduate references ^[3][5][6].

What is the Markov property?

The Markov property is the requirement that, given the present state, the future of the process is conditionally independent of its entire past. In Norris's words, the characteristic property of a Markov process is that it retains "no memory of where it has been in the past" ^[3]: the past and the future are independent given the present. This single assumption is what reduces an otherwise intractable joint distribution over an infinite sequence to a product of one-step transition probabilities. Enlarging the state space to include enough recent history can make almost any process Markovian, which is why the property is so widely usable in modelling ^[3][5].

What is a discrete-time Markov chain?

A discrete-time Markov chain is specified by a state space S, a transition function $p(i, j)$, and an initial distribution $\mu_0$. When S is finite or countable, the transition probabilities form a matrix P with $P_{ij} = P(X_{n+1} = j \mid X_n = i)$. Each row of P is non-negative and sums to one, which makes P a row-stochastic matrix ^[3]. The distribution of $X_n$ is $\mu_0 P^n$. The (i, j) entry of $P^n$ is the probability of moving from i to j in exactly n steps, and the relation generalises to the Chapman-Kolmogorov equation $P^{m+n} = P^m P^n$ ^[23].

Three illustrative examples: a two-state weather chain ($P_{ss} = 0.8$, $P_{sr} = 0.2$, $P_{rs} = 0.5$, $P_{rr} = 0.5$) settles to a long-run distribution roughly 71 percent sunny; the simple random walk on $\mathbb{Z}$ with $P_{i, i+1} = p$, $P_{i, i-1} = 1 - p$ is recurrent if and only if $p = 1/2$; the Ehrenfest urn model places N balls in two boxes and moves a uniformly chosen ball at each step, giving a birth-death chain on $\{0, 1, \ldots, N\}$ with reflecting boundaries ^[3]. For a finite chain, P is a finite-dimensional linear operator and most questions reduce to linear algebra.

What is a continuous-time Markov chain?

A continuous-time Markov chain is a process $(X_t)_{t \ge 0}$ on a discrete state space S such that, for $s < t$, the conditional distribution of $X_t$ given the history up to s depends only on $X_s$. It is described by a generator matrix $Q$ whose off-diagonal entries $q_{ij}$ are non-negative transition rates from i to j and whose diagonal entries $q_{ii} = -\sum_{j \ne i} q_{ij}$ make rows sum to zero ^[3].

The holding time in state i is exponentially distributed with rate $-q_{ii}$, and on leaving state i the chain jumps to j with probability $q_{ij} / (-q_{ii})$. The transition semigroup $P(t)$ satisfies Kolmogorov's forward and backward equations $dP/dt = PQ$ and $dP/dt = QP$, with solution $P(t) = \exp(Qt)$ for finite state spaces ^[23]. Continuous-time chains are the natural setting for queuing theory (M/M/1 and M/M/c queues), reliability analysis, and continuous-time models of molecular evolution.

How are the states of a Markov chain classified?

Two states i and j communicate if each can be reached from the other in finitely many steps; communication is an equivalence relation whose classes are called communicating classes. A chain is irreducible if there is only one communicating class ^[3].

Scroll sideways for more →

For a finite chain every state is transient or positive recurrent, and a finite irreducible chain is automatically positive recurrent ^[3]. For infinite chains the picture is richer. The simple symmetric random walk on $\mathbb{Z}$ is null recurrent: it returns with probability 1 but the expected time to return is infinite. The asymmetric random walk on $\mathbb{Z}$ ($p \ne 1/2$) is transient and drifts to infinity.

George Polya (1921) proved that the simple symmetric random walk on $\mathbb{Z}^d$ is recurrent for $d = 1$ and $d = 2$ and transient for $d \ge 3$ ^[20]. The dimensional cutoff is sometimes summarised by the phrase "a drunk man finds his way home but a drunk bird may get lost forever".

What is a stationary distribution?

A distribution $\pi$ on S is stationary (or invariant) for the chain with transition matrix P if $\pi P = \pi$, that is $\sum_i \pi_i P_{ij} = \pi_j$ for every j. Equivalently, $\pi$ is a left eigenvector of P with eigenvalue 1. If the chain starts in $\pi$ it remains in $\pi$ forever: $P(X_n = j) = \pi_j$ for every n ^[3][4].

The central convergence result is the ergodic theorem: for an irreducible, aperiodic, positive recurrent chain on a countable state space, the stationary distribution $\pi$ exists and is unique, and for every initial distribution $\mu_0$ the distribution $\mu_0 P^n$ converges to $\pi$ in total variation distance ^[3][6]. For finite chains, existence of $\pi$ follows from the Perron-Frobenius theorem: an irreducible non-negative matrix has a largest eigenvalue of multiplicity one with a strictly positive eigenvector.

A chain is reversible with respect to $\pi$ if the detailed balance equations $\pi_i P_{ij} = \pi_j P_{ji}$ hold for every pair (i, j). Detailed balance is sufficient (but not necessary) for stationarity: sum the equations over i to get $\pi P = \pi$. The local equations are usually much easier to solve than the global stationarity equations, and almost every MCMC algorithm constructs a reversible chain whose stationary distribution is the target ^[7][14].

For a finite irreducible chain there is also a clean characterisation: the stationary probability of state i equals $1 / \mathbb{E}_i[T_i]$, where $T_i$ is the first return time to i (the Kac formula) ^[6].

How fast does a Markov chain converge (mixing times)?

The ergodic theorem says $\mu_0 P^n$ converges to $\pi$ but not how fast. Quantifying the speed of convergence is the subject of mixing-time theory, an active area since the 1980s ^[6]. The standard measure of distance to stationarity is the total variation distance $d(n) = \max_{\mu_0} \lVert \mu_0 P^n - \pi \rVert_{\mathrm{TV}}$; the mixing time with tolerance $\epsilon$ is $t_{\mathrm{mix}}(\epsilon) = \min\{n : d(n) \le \epsilon\}$, with $\epsilon = 1/4$ a common choice.

For a reversible chain the eigenvalues of P are real and lie in $[-1, 1]$, and the rate of convergence is governed by the second-largest eigenvalue in absolute value, $\lambda_*$. The spectral gap $\gamma = 1 - \lambda_*$ bounds the mixing time: roughly $t_{\mathrm{mix}}$ is on the order of $(1/\gamma) \log(1/\pi_{\min})$, where $\pi_{\min}$ is the smallest stationary probability ^[6]. Lower bounds use conductance (the Cheeger inequality) and canonical paths.

The cutoff phenomenon, studied since the work of Aldous, Diaconis, and Shahshahani in the early 1980s, occurs in many natural families of chains: the distance to stationarity stays close to 1 for a long time and then drops abruptly to nearly 0 in a window much shorter than the mixing time itself ^[6]. The classical example is the riffle-shuffle Markov chain, where seven shuffles suffice to mix a 52-card deck (Bayer and Diaconis, 1992) ^[19].

Hitting times and absorption probabilities

For a state j the hitting time T_j is the first time the chain visits j; hitting times satisfy a linear system solvable efficiently for finite chains ^[3]. For an absorbing chain, arrange P = [[Q, R], [0, I]] with Q the transition matrix among transient states and R from transient to absorbing states. The fundamental matrix $N = (I - Q)^{-1}$ has entry $N_{ij}$ equal to the expected number of visits to transient state j starting from i, and absorption probabilities are given by $NR$ ^[4]. The classical gambler's ruin, in which a gambler with fortune k bets on fair coin tosses until reaching 0 (ruin) or N (target), is the canonical example: the probability of reaching N before 0 is $k / N$ for fair play.

Examples

Scroll sideways for more →

The Ehrenfest urn was introduced by Paul and Tatiana Ehrenfest in 1907 to clarify the apparent paradox between microscopic reversibility and macroscopic entropy increase.

How are Markov chains used in AI and machine learning?

Markov chains underpin a striking share of probabilistic machine learning: hide the state and you get a hidden Markov model; add actions and rewards and you get a Markov decision process, the formal foundation of reinforcement learning; construct a chain whose long-run distribution is a target and you get Markov chain Monte Carlo; run a chain on the web graph and its stationary distribution is PageRank ^{[8][9][11][14]}.

Scroll sideways for more →

These are variations on a common theme: model the system as a Markov chain (possibly with actions, rewards, or partial observations) and then analyse it. Most stochastic processes can be rendered Markovian by enlarging the state space to include enough of the recent history ^[3].

What is Markov chain Monte Carlo (MCMC)?

Markov chain Monte Carlo (MCMC) is the application that has done the most to spread Markov-chain theory beyond probabilists. The idea, originating with Metropolis and others at Los Alamos in the early 1950s and generalised by Hastings (1970), is to construct a Markov chain whose stationary distribution is some target pi (often the posterior in a Bayesian model) and run the chain long enough to draw approximate samples ^[14]. The Gibbs sampler (Geman and Geman, 1984) and the Metropolis-Hastings algorithm are the workhorses ^[15]; Hamiltonian Monte Carlo (Duane et al., 1987) and the No-U-Turn Sampler (Hoffman and Gelman, 2014) underlie Stan and PyMC. Robert and Casella's Monte Carlo Statistical Methods (2004) is the standard reference ^[7]. Almost every MCMC algorithm relies on detailed balance to certify that the chain has the right stationary distribution.

How is PageRank a Markov chain?

Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd introduced PageRank in 1998 as the ranking core of the Google search engine ^[9][10]. The algorithm models a "random surfer" who at each step either follows a uniformly random outgoing link from the current page (with probability $d$, the damping factor, typically 0.85) or teleports to a uniformly random page (with probability $1 - d$) ^[9]. This is a Markov chain on the set of web pages: in the words of the canonical description, PageRank "can be understood as a Markov chain in which the states are pages, and the transitions are the links between pages" ^[9]. Teleportation ensures the chain is irreducible and aperiodic, so the stationary distribution exists and is unique by the ergodic theorem; that stationary distribution is PageRank. Computationally PageRank reduces to power iteration on a matrix with billions of rows.

How do Markov chains relate to reinforcement learning and MDPs?

A Markov decision process generalises a Markov chain by allowing an agent to choose actions at each state that influence the transition probabilities and produce a reward. Richard Bellman introduced MDPs in 1957 in the context of dynamic programming ^[12]; Howard's 1960 monograph Dynamic Programming and Markov Processes gave the first textbook treatment ^[13]. Sutton and Barto's Reinforcement Learning: An Introduction (1998, second edition 2018) made MDPs the central object of modern RL ^[8]. Value iteration, policy iteration, Q-learning, SARSA, actor-critic, and PPO are all algorithms for learning or computing optimal policies on an MDP. When the state is only partially observed, the model becomes a partially observable MDP (POMDP), studied since Astrom (1965) and Smallwood and Sondik (1973).

How do diffusion models use Markov chains?

Diffusion-based generative models, which now dominate text-to-image generation, are built on Markov chains in time. Sohl-Dickstein, Weiss, Maheswaranathan, and Ganguli (2015) introduced deep unsupervised learning using nonequilibrium thermodynamics, framing image generation as the reverse of a Markov chain that gradually adds Gaussian noise to data ^[16]. Ho, Jain, and Abbeel (2020) refined this into the Denoising Diffusion Probabilistic Model (DDPM), which trains a neural network to predict the noise added at each step of the forward chain and then runs the learned reverse chain to sample new images; on unconditional CIFAR-10 it reported an Inception score of 9.46 and a FID of 3.17 ^[17]. Both forward (noising) and reverse (denoising) processes are explicit Markov chains in the time index; DDPM's loss derives from a variational bound on the Markov-chain likelihood. Score-based generative models (Song and Ermon, 2019; Song et al., 2021) are equivalent in continuous time and connect the construction to stochastic differential equations.

How do Markov chains connect to information theory?

The entropy rate of a stationary Markov chain is $H(X_1 \mid X_0) = -\sum_i \pi_i \sum_j P_{ij} \log P_{ij}$, the average uncertainty about the next state given the current one; this is the long-run information rate of the chain in the sense of Shannon ^[21]. The asymptotic equipartition property and the Shannon-McMillan-Breiman theorem extend from independent sequences to ergodic Markov chains, with the entropy rate playing the role of per-symbol entropy. In data compression, n-gram models (themselves Markov chains over symbols) appear as workhorses of pre-neural language modelling ^[21].

Continuous-state and continuous-time generalisations

Many of the concepts above extend to continuous state spaces, with sums replaced by integrals and matrices replaced by integral kernels. The general framework is the theory of Markov processes, which subsumes:

Scroll sideways for more →

Brownian motion, introduced by Einstein (1905) and rigorously constructed by Wiener (1923), is the canonical continuous-state continuous-time Markov process and is the limit of suitably scaled simple random walks. Stochastic differential equations $dX_t = b(X_t)\, dt + \sigma(X_t)\, dW_t$ define diffusion processes, which are Markov by construction. Levy processes (Levy 1937) generalise further to allow jumps.

How does a Markov chain differ from related models?

Scroll sideways for more →

The Markov chain sits at the centre of this taxonomy, with related models extending it: hide the state, add actions, take a continuous-time or continuous-state limit, or drop the directionality. Almost every probabilistic model used in modern machine learning either is a Markov chain, contains one, or is a close graphical-model relative.

What software implements Markov chains?

Scroll sideways for more →

For small chains numpy is sufficient; for continuous-time chains scipy.linalg computes $P(t) = \exp(Qt)$ directly; for very large chains (as in PageRank) sparse matrices and the power method are standard.

Famous results

Scroll sideways for more →

See also

• Markov property
• Hidden Markov model
• Markov decision process (MDP)
• Markov chain Monte Carlo
• Reinforcement learning
• Diffusion model

References

1. Markov, A. A. (1906). "Distribution of the law of large numbers for quantities depending on one another" (Extension of the law of large numbers to dependent variables). *Izvestiya Fiziko-Matematicheskogo Obshchestva pri Kazanskom Universitete*, 2nd series, 15, 135-156. ↩
2. Markov, A. A. (1913). "An example of statistical investigation of the text Eugene Onegin concerning the connection of samples in chains". *Bulletin of the Imperial Academy of Sciences*, Saint Petersburg. ↩
3. Norris, J. R. (1997). *Markov Chains*. Cambridge University Press. ↩
4. Kemeny, J. G., and Snell, J. L. (1960). *Finite Markov Chains*. Van Nostrand; reprinted by Springer. ↩
5. Grimmett, G. R., and Stirzaker, D. R. (2001). *Probability and Random Processes*, third edition. Oxford University Press. ↩
6. Levin, D. A., and Peres, Y. (2017). *Markov Chains and Mixing Times*, second edition (with E. L. Wilmer). American Mathematical Society. ↩
7. Robert, C. P., and Casella, G. (2004). *Monte Carlo Statistical Methods*, second edition. Springer. ↩
8. Sutton, R. S., and Barto, A. G. (2018). *Reinforcement Learning: An Introduction*, second edition. MIT Press. ↩
9. Page, L., Brin, S., Motwani, R., and Winograd, T. (1999). "The PageRank Citation Ranking: Bringing Order to the Web". Stanford InfoLab Technical Report 1999-66. ↩
10. Brin, S., and Page, L. (1998). "The anatomy of a large-scale hypertextual Web search engine". *Computer Networks and ISDN Systems*, 30(1-7), 107-117. ↩
11. Rabiner, L. R. (1989). "A tutorial on hidden Markov models and selected applications in speech recognition". *Proceedings of the IEEE*, 77(2), 257-286. ↩
12. Bellman, R. (1957). *Dynamic Programming*. Princeton University Press. ↩
13. Howard, R. A. (1960). *Dynamic Programming and Markov Processes*. MIT Press. ↩
14. Hastings, W. K. (1970). "Monte Carlo sampling methods using Markov chains and their applications". *Biometrika*, 57(1), 97-109. ↩
15. Geman, S., and Geman, D. (1984). "Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images". *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 6(6), 721-741. ↩
16. Sohl-Dickstein, J., Weiss, E. A., Maheswaranathan, N., and Ganguli, S. (2015). "Deep unsupervised learning using nonequilibrium thermodynamics". *Proceedings of the 32nd International Conference on Machine Learning*. ↩
17. Ho, J., Jain, A., and Abbeel, P. (2020). "Denoising diffusion probabilistic models". *Advances in Neural Information Processing Systems* 33. ↩
18. Propp, J. G., and Wilson, D. B. (1996). "Exact sampling with coupled Markov chains and applications to statistical mechanics". *Random Structures and Algorithms*, 9(1-2), 223-252.
19. Bayer, D., and Diaconis, P. (1992). "Trailing the dovetail shuffle to its lair". *Annals of Applied Probability*, 2(2), 294-313. ↩
20. Polya, G. (1921). "Uber eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz". *Mathematische Annalen*, 84, 149-160. ↩
21. Shannon, C. E. (1948). "A mathematical theory of communication". *Bell System Technical Journal*, 27, 379-423 and 623-656. ↩
22. Doob, J. L. (1953). *Stochastic Processes*. Wiley. ↩
23. Kolmogorov, A. N. (1931). "Uber die analytischen Methoden in der Wahrscheinlichkeitsrechnung". *Mathematische Annalen*, 104, 415-458. ↩
24. Hayes, B. (2013). "First Links in the Markov Chain". *American Scientist*, 101(2), 92. ↩