In 1913, Andrei Markov took the first 20,000 letters of Pushkin’s Eugene Onegin, classified each as a vowel or a consonant, and counted how often each followed the other. He was not doing literary criticism. He was making a point in a mathematical argument : that the law of large numbers survives even when observations are not independent, provided each one depends only on the one immediately before it (Markov, 1913). 1 That single restriction — the future depends on where you are, not on how you got there — turned out to describe an enormous amount of the world, and ninety years later it was worth roughly the market capitalisation of Google. This post builds Markov chains from that assumption, works out where they settle down and how fast, and then shows how PageRank is nothing more than one very large chain’s stationary distribution.
one assumption, and the matrix that encodes it
1. The memoryless assumption
Imagine a system that moves between a finite set of states — sunny, cloudy, rainy ; a page you are reading ; a square on a board. At each step it jumps somewhere according to some probabilities. The Markov assumption says those probabilities depend on exactly one thing : where you are right now.
In plain words : the chain has no memory. It does not know how it arrived, how long it has been wandering, or where it started. It only knows where it is standing, and that is enough to decide where it goes next.
There is one confusion worth killing immediately, because almost everyone makes it once. Memoryless does not mean independent. Tomorrow’s weather is strongly dependent on today’s — that is the whole point. What the assumption rules out is a dependence on yesterday’s weather given that you already know today’s.
2. The transition matrix
Collect all the one-step probabilities $p_{ij}$ into a matrix $P$. Row $i$ holds everything that can happen when you are in state $i$, so every row sums to one — a matrix with that property is called row-stochastic.
For the weather chain in figure 1, ordering the states as (sunny, cloudy, rainy) :
\[\begin{equation} P = \begin{pmatrix} 0.70 & 0.25 & 0.05 \\ 0.35 & 0.40 & 0.25 \\ 0.20 & 0.45 & 0.35 \end{pmatrix}. \label{eq:P} \end{equation}\]Now write the current belief about where you are as a row vector $\pi = (\pi_S, \pi_C, \pi_R)$ summing to one. One step forward is a single matrix multiplication :
\[\begin{equation} \pi_{n+1} = \pi_n P, \qquad\text{and therefore}\qquad \pi_n = \pi_0 P^{\,n}. \label{eq:step} \end{equation}\]Check the first one by hand on a single entry. The chance of being cloudy tomorrow is “the chance it is sunny today times the chance sunny leads to cloudy”, plus the same for cloudy and for rainy — which is precisely the second component of the product $\pi P$. Matrix multiplication is doing the law of total probability for you, all three states at once.
The second half of $\eqref{eq:step}$ is more than notation. It says that $n$ steps of a Markov chain is the $n$-th power of a matrix, and it comes with a clean interpretation.
Proof. By induction. It holds for $n = 1$ by definition. Suppose it holds for $n$. To get from $i$ to $j$ in $n+1$ steps you must pass through some state $k$ at step $n$, and those routes are disjoint, so by the law of total probability $$ \mathbb{P}(X_{n+1}=j \mid X_0 = i) = \sum_k \mathbb{P}(X_n = k \mid X_0 = i)\; p_{kj} = \sum_k (P^{\,n})_{ik}\, p_{kj} = (P^{\,n+1})_{ij}, $$ where the middle step used the Markov property to drop the history before step $n$.
$\square$
So the entire long-run behaviour of the chain is a question about powers of a matrix, which is a question about its eigenvalues. That is the bridge from probability to linear algebra, and everything in Part II crosses it.
where it settles, whether that is unique, and how fast it gets there
3. The stationary distribution
Figure 2 shows something remarkable : as you raise $P$ to higher powers, the rows become identical. That means the chain forgets its starting point entirely. Whatever the weather today, the probability that it is raining a month from now is the same number.
Read that equation again with linear-algebra eyes. It says $\pi$ is a left eigenvector of $P$ with eigenvalue 1 — and $1$ is always an eigenvalue of a row-stochastic matrix, because the all-ones column vector satisfies $P\mathbf{1} = \mathbf{1}$ (each row sums to one). So a stationary distribution always exists for a finite chain.
In plain words : the stationary distribution is the mixture that reproduces itself. Put 60 % of your probability on sunny and the rest split appropriately, run one day forward, and you get the identical mixture back. It is the equilibrium the system relaxes into.
For the weather chain, solving $\pi = \pi P$ together with $\sum \pi_i = 1$ gives
\[\pi \;\approx\; (0.4949,\; 0.3232,\; 0.1818),\]so in the long run it is sunny about half the time, cloudy a third, rainy a sixth — regardless of what it is doing today. There is a second, very useful reading of the same numbers : $\pi_i$ is the fraction of time the chain spends in state $i$ over a long run, and $1/\pi_i$ is the average number of steps between successive visits to it.
4. When does it actually converge ?
Here is where most treatments wave their hands, and where the interesting failures live. Existence of $\pi$ is free. Uniqueness and convergence are not, and each needs its own condition.
A chain is aperiodic if it is not locked into a cycle : formally, the greatest common divisor of the possible return times to a state is 1.
Lose irreducibility and uniqueness goes. If the graph splits into two pieces that cannot reach each other, each piece has its own equilibrium, and any blend of the two is also stationary. There is no single answer to “where does it end up” because the answer depends on which half you started in. This is not an exotic corner case — it is exactly what the web looks like, and section 6 is about the trick that repairs it.
Lose aperiodicity and convergence goes, even though $\pi$ is still unique. Take a chain that must move $A \to B \to C \to A$ every step. Start at $A$ and after $n$ steps you are at $A$, $B$ or $C$ depending only on $n \bmod 3$ — the distribution oscillates forever and never settles. The stationary distribution $(1/3, 1/3, 1/3)$ is perfectly well defined and describes the long-run time average, but $P^n$ does not converge to anything. Adding a single self-loop anywhere breaks the cycle and fixes it.
5. How fast ? The second eigenvalue
Convergence is guaranteed, but a guarantee with no rate is useless in practice. The rate is controlled by one number.
For an irreducible aperiodic chain the eigenvalues satisfy $\lambda_1 = 1 > \lvert\lambda_2\rvert \ge \lvert\lambda_3\rvert \ge \cdots$, and the distance to equilibrium decays like the second-largest one :
\[\begin{equation} \big\lVert \pi_0 P^{\,n} - \pi \big\rVert \;\le\; C\,\lvert\lambda_2\rvert^{\,n}. \label{eq:gap} \end{equation}\]The quantity $1 - \lvert\lambda_2\rvert$ is the spectral gap, and the number of steps needed to get close to equilibrium — the mixing time — scales roughly as $1/(1 - \lvert\lambda_2\rvert)$ (Levin & Peres, 2017).
In plain words : $\lambda_2$ measures how bottlenecked the chain is. If the state space has two well-connected regions joined by one narrow bridge, the chain will equilibrate quickly inside each region and then take a very long time to balance across the bridge. That slow crossing is $\lambda_2$, and it is close to 1. A chain that mixes everything freely has a small $\lvert\lambda_2\rvert$ and forgets its start almost immediately.
This is not an abstract concern. It is the single most important practical question about any chain you build : in section 8, it decides whether your Bayesian sampler gives you an answer in an hour or in a geological age.
ranking the web, hidden states, and turning the whole thing around
6. PageRank : a chain the size of the web
Here is the idea that made Part II worth a fortune. Model the web as a graph : pages are states, links are transitions. Now imagine a random surfer who starts anywhere and repeatedly clicks a link chosen uniformly at random from the current page (Brin & Page, 1998)(Page et al., 1999).
Where does this surfer spend their time ? That is exactly the stationary distribution question from section 3 — and its answer is a ranking. A page is important if the surfer is often on it, which happens when many pages link to it, and especially when important pages link to it. The definition is recursive, which sounds circular and is in fact just an eigenvector equation.
There are two problems, and both are failures of the conditions in section 4.
- Dangling pages. A page with no outgoing links is a dead end : the surfer arrives and the probability leaks out of the system. The row of $P$ is all zeros and it is not a stochastic matrix any more.
- The web is not irreducible. It is full of pieces that link inward but never back out, so by section 4 there is no unique answer.
The fix is one line, and it repairs both at once. With probability $d \approx 0.85$ the surfer follows a link ; with probability $1-d$ they get bored and teleport to a page chosen uniformly at random :
\[\begin{equation} G \;=\; d\,P \;+\; \frac{1-d}{N}\,J, \qquad J = \text{the all-ones matrix.} \label{eq:google} \end{equation}\]In plain words : the teleport is not a hack bolted on to fix bad data. It is the thing that makes the question well posed at all, and the damping factor is simultaneously the knob that guarantees the answer is unique and the knob that controls how fast you can compute it. This is a genuinely satisfying case of Perron–Frobenius theory (Frobenius, 1912) paying rent.
Computing it needs no eigenvalue solver. Just apply $\eqref{eq:step}$ repeatedly — power iteration — and $\eqref{eq:gap}$ guarantees you converge.
def pagerank(links, n, d=0.85, iters=60):
"""links[i] = list of pages that page i points to."""
out = [len(links[i]) for i in range(n)]
rank = [1.0 / n] * n
for _ in range(iters):
new = [(1 - d) / n] * n
leak = 0.0
for i in range(n):
if out[i] == 0:
leak += d * rank[i] / n # dangling page
else:
share = d * rank[i] / out[i]
for j in links[i]:
new[j] += share
rank = [r + leak for r in new]
return rank
Figure 5 makes the recursive definition concrete. Four unremarkable pages point at the hub, so the hub accumulates their weight. The hub then points at a single page — and that page, with one incoming link, ends up ranked almost as highly as the hub with its five. That is the whole insight : links are votes, but votes are weighted by the voter’s own standing.
7. When you cannot see the state
Often the chain is real but invisible. You do not observe the states, only noisy consequences of them : you hear sounds, not phonemes ; you read words, not grammatical categories ; you sequence DNA, not the genes’ functional regions. A hidden Markov model adds a second layer — a Markov chain over hidden states, plus an emission distribution giving what you observe from each (Rabiner, 1989).
Three questions follow, and each has a clean algorithm. How likely is this observation sequence ? (the forward algorithm.) What is the most probable hidden path that produced it ? (the Viterbi algorithm (Viterbi, 1967).) And how do I learn the parameters from data alone ? (Baum–Welch.)
8. Turning the whole thing around : MCMC
Everything so far asked : given a chain, what does it converge to ? One of the best ideas in computational statistics is to run that question backwards. Given a distribution you want to sample from, design a chain that converges to it.
This matters because in Bayesian inference you routinely end up with a posterior you can evaluate up to an unknown constant but cannot integrate, sample, or even normalise. Metropolis and colleagues (Metropolis et al., 1953), later generalised by Hastings (Hastings, 1970), found a chain whose stationary distribution is any target $p$ you like :
- From the current point $x$, propose a nearby $x’$.
- Accept it with probability $\min!\big(1,\; p(x’)/p(x)\big)$ ; otherwise stay at $x$.
The unknown normalising constant cancels in the ratio, which is the trick. The chain provably has $p$ as its stationary distribution, so after enough steps its visits are draws from $p$ — and “enough steps” is the mixing time of section 5. A badly designed proposal makes $\lvert\lambda_2\rvert$ close to 1, the chain crawls, and you get thousands of samples that are all essentially the same point. Every practical difficulty with MCMC is a spectral gap problem in disguise.
9. Where the assumption breaks
Real sequences have memory. Language certainly does : the word after “the capital of France is” depends on all six words, not just on “is”.
The standard repair is to enlarge the state until the assumption becomes true. Make the state the last $k$ words rather than the last one, and you have an $n$-gram model, which is genuinely Markov again. The cost is brutal : with a vocabulary of $V$ words the state space is $V^{k}$, so it explodes exponentially and you never have enough data to estimate the transitions. This is why $n$-gram language models stalled at $k = 5$ or so for decades.
Two other honest limitations. Real chains are often non-stationary — the transition probabilities themselves drift over time, and a model fitted last year quietly stops applying. And the discrete-state picture forces you to bin continuous quantities, which is a modelling choice that can matter more than the chain itself.
10. Conclusion
A Markov chain is one assumption — the future depends only on the present — and everything else is consequence.
Encode the assumption as a matrix and $n$ steps become the $n$-th power, which turns a probabilistic question into a question about eigenvalues. The eigenvalue $1$ gives the equilibrium the chain relaxes into ; irreducibility makes that equilibrium unique ; aperiodicity makes the chain actually reach it ; and the second eigenvalue says how long you will be waiting. Those four facts are the whole theory, and they are enough to explain why adding a 15 % chance of teleporting to a random page is what makes ranking the entire web both well defined and computable in fifty iterations.
The assumption is also a design choice, not a law of nature. When it is false, you can enlarge the state until it becomes true and pay in exponential blow-up — or you can abandon it, which is the road that led to attention. Knowing which of those you are doing, and why, is most of the value in understanding the chain in the first place.
References
- Brin, S., & Page, L. (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 30(1–7), 107–117.
@article{Brin1998, author = {Brin, Sergey and Page, Lawrence}, title = {The Anatomy of a Large-Scale Hypertextual Web Search Engine}, journal = {Computer Networks and ISDN Systems}, volume = {30}, number = {1--7}, pages = {107--117}, year = {1998} } - Frobenius, G. (1912). Über Matrizen aus nicht negativen Elementen. Sitzungsberichte Der Königlich Preussischen Akademie Der Wissenschaften, 456–477.
@article{Frobenius1912, author = {Frobenius, Georg}, title = {{\"U}ber Matrizen aus nicht negativen Elementen}, journal = {Sitzungsberichte der K{\"o}niglich Preussischen Akademie der Wissenschaften}, pages = {456--477}, year = {1912} } - Hastings, W. K. (1970). Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika, 57(1), 97–109.
@article{Hastings1970, author = {Hastings, W. Keith}, title = {Monte Carlo Sampling Methods Using Markov Chains and Their Applications}, journal = {Biometrika}, volume = {57}, number = {1}, pages = {97--109}, year = {1970} } - Levin, D. A., & Peres, Y. (2017). Markov Chains and Mixing Times (2nd ed.). American Mathematical Society.
@book{Levin2017, author = {Levin, David A. and Peres, Yuval}, title = {Markov Chains and Mixing Times}, edition = {2nd}, year = {2017}, publisher = {American Mathematical Society} } - Markov, A. A. (1913). An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains. Science in Context (English Translation, 2006), 19(4), 591–600.
@article{Markov1913, author = {Markov, Andrei A.}, title = {An Example of Statistical Investigation of the Text {Eugene Onegin} Concerning the Connection of Samples in Chains}, journal = {Science in Context (English translation, 2006)}, volume = {19}, number = {4}, pages = {591--600}, year = {1913} } - Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6), 1087–1092.
@article{Metropolis1953, author = {Metropolis, Nicholas and Rosenbluth, Arianna W. and Rosenbluth, Marshall N. and Teller, Augusta H. and Teller, Edward}, title = {Equation of State Calculations by Fast Computing Machines}, journal = {The Journal of Chemical Physics}, volume = {21}, number = {6}, pages = {1087--1092}, year = {1953} } - Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank Citation Ranking: Bringing Order to the Web (No.1999-66; Numbers 1999-66). Stanford InfoLab.
@techreport{Page1999, author = {Page, Lawrence and Brin, Sergey and Motwani, Rajeev and Winograd, Terry}, title = {The PageRank Citation Ranking: Bringing Order to the Web}, institution = {Stanford InfoLab}, number = {1999-66}, year = {1999} } - Rabiner, L. R. (1989). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77(2), 257–286.
@article{Rabiner1989, author = {Rabiner, Lawrence R.}, title = {A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition}, journal = {Proceedings of the IEEE}, volume = {77}, number = {2}, pages = {257--286}, year = {1989} } - Viterbi, A. J. (1967). Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm. IEEE Transactions on Information Theory, 13(2), 260–269.
@article{Viterbi1967, author = {Viterbi, Andrew J.}, title = {Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm}, journal = {IEEE Transactions on Information Theory}, volume = {13}, number = {2}, pages = {260--269}, year = {1967} }
-
Markov’s choice of Eugene Onegin was polemical. He was in a long argument with Pavel Nekrasov, who had claimed that the law of large numbers required independence and therefore that its appearance in social statistics was evidence of free will. Markov’s vowel-and-consonant counts were a deliberate counterexample : here is a sequence that is plainly not independent, and the law of large numbers holds anyway. The theory of stochastic processes began as a rebuttal in a philosophical dispute. ↩