When this article was written, the site had 825 pages, joined by 9,200 links written into their text. Imagine a reader who opens one page, picks one of its links at random, follows it, and repeats, forever. Where does such a reader spend the long run? Does the answer depend on the starting page? How many clicks does it take to forget where the reading began? On this site the answers are sharp. A reader who only follows links is caught, after about 30,000 clicks from almost any page, by three pages that link only to one another. A reader who also jumps to a random page with probability 0.15 at each click, as PageRank assumes, settles into one long-run distribution from every start and forgets the start within a few dozen clicks. The theory of Markov chains says why.
A Markov chain is a sequence of random states in which the next state depends on the past only through the present one. The reader's page after the next click depends on the current page and on nothing earlier. That one property, with finitely many states, is enough to settle the three questions: whether a long-run distribution exists, whether it is unique, and whether, and how fast, the chain approaches it. This article proves those results in full for finite chains. It is the unit's home for them, and Hidden Markov Models, Random Walks and Martingales and Autocorrelation and Stationarity build on it.
Here is the route. First the definition, the transition matrix and the Chapman–Kolmogorov equations, on a three-state weather chain small enough to check by hand. Then the structure of a chain, its communicating classes, read off the site's link graph. Then stationary distributions: one exists for every finite chain, it is unique and positive when every state can reach every other, and each stationary probability is the reciprocal of a mean return time. Then convergence: periodicity, the theorem that an irreducible aperiodic chain is regular, and convergence to the stationary distribution at a geometric rate. Then the ergodic theorem, which turns stationary probabilities into long-run fractions of time along one path. Then absorbing chains, which answer the question of how long the surfer wanders before being caught. Finally reversibility, the random walk on an undirected graph, and a bound on the distance from stationarity from the second eigenvalue. The article assumes Random Variables, Expectation and Variance and Conditional Probability and the Law of Total Probability; one proof uses the strong law of The Laws of Large Numbers.
Notation and the scope of the proofs
The state space $S$ is a finite set of $m$ states, labeled $i, j, k$. The chain is $X_0, X_1, X_2, \ldots$, with time written $n$. The transition probabilities are $p_{ij} = P(X_{n+1} = j \mid X_n = i)$, the same at every time, collected in the $m \times m$ transition matrix $P = (p_{ij})$. Each row of $P$ is a probability distribution over the next state, so its entries are nonnegative and its rows sum to 1; such a matrix is called stochastic. Distributions on $S$ are row vectors: the initial distribution is $\mu$, with $\mu_i = P(X_0 = i)$. The column vector of ones is $\mathbf{1}$, so $P\mathbf{1} = \mathbf{1}$ says that the rows sum to 1. $P_i$ and $E_i$ are probability and expectation for the chain started at state $i$. These conventions are those of PageRank and Markov Chain Monte Carlo.
Every proof below is for a finite state space and uses sums only. Chains on countably many states, such as the random walks of Random Walks and Martingales, and on continuous spaces, such as the samplers of Markov Chain Monte Carlo, need the general theory, which is cited where it is mentioned.
Transition probabilities and the Chapman–Kolmogorov equations
Grinstead and Snell (1997, Example 11.1) give a chain small enough to compute with by hand, which they credit to Kemeny, Snell and Thompson. In the Land of Oz the weather each day is rain (R), nice (N) or snow (S). There are never two nice days in a row. After a nice day, snow and rain are equally likely. After rain or snow, the same weather follows with probability one half, and a change goes to each of the other two kinds with probability one quarter. In the order R, N, S,
$$P = \begin{pmatrix} 1/2 & 1/4 & 1/4 \\ 1/2 & 0 & 1/2 \\ 1/4 & 1/4 & 1/2 \end{pmatrix}.$$
The Markov property. A sequence $X_0, X_1, \ldots$ is a Markov chain with initial distribution $\mu$ and transition matrix $P$ when, for every $n$ and every sequence of states,
$$P(X_0 = i_0, X_1 = i_1, \ldots, X_n = i_n) = \mu_{i_0}\,p_{i_0i_1}\,p_{i_1i_2}\cdots p_{i_{n-1}i_n}. \qquad (1)$$
Equation (1) is the definition used throughout: the probability of a path is the initial probability of its first state times the transition probabilities along it. Dividing (1) by the same expression for $n - 1$ gives $P(X_n = i_n \mid X_0 = i_0, \ldots, X_{n-1} = i_{n-1}) = p_{i_{n-1}i_n}$ whenever the condition has positive probability: the next state depends on the past only through the present state.
What is the probability of snow two days after rain? Two days pass through an intermediate day, which is rain, nice or snow. Adding over the three gives $\frac12 \cdot \frac14 + \frac14 \cdot \frac12 + \frac14 \cdot \frac12 = \frac38$, the $(R, S)$ entry of $P^2$. In general, the probabilities of $n$ steps are the entries of the $n$-th power of $P$.
Theorem 1 (Chapman–Kolmogorov). Write $p_{ij}^{(n)} = P(X_n = j \mid X_0 = i)$. Then $p_{ij}^{(n)} = (P^n)_{ij}$, and for all $a, b \ge 0$,
$$p_{ij}^{(a+b)} = \sum_{k \in S} p_{ik}^{(a)}\,p_{kj}^{(b)}. \qquad (2)$$
The distribution of $X_n$ is the row vector $\mu P^n$.
Proof. Start at $i$, so $\mu_i = 1$. By (1), $P_i(X_n = j)$ is the sum over all paths $i = i_0, i_1, \ldots, i_{n-1}, i_n = j$ of $p_{i_0i_1}\cdots p_{i_{n-1}i_n}$. That sum over the intermediate states $i_1, \ldots, i_{n-1}$ is exactly the definition of the $(i, j)$ entry of the matrix product $P \cdot P \cdots P$ with $n$ factors. So $p_{ij}^{(n)} = (P^n)_{ij}$, and (2) is the entry $(i, j)$ of $P^{a+b} = P^aP^b$. For a general start, $P(X_n = j) = \sum_i \mu_i P_i(X_n = j) = \sum_i \mu_i (P^n)_{ij} = (\mu P^n)_j$, using (1) again: a path from $i$ has probability $\mu_i$ times its transition probabilities. $\square$
For the Land of Oz, the matrix of two-day probabilities is
$$P^2 = \begin{pmatrix} 7/16 & 3/16 & 3/8 \\ 3/8 & 1/4 & 3/8 \\ 3/8 & 3/16 & 7/16 \end{pmatrix}.$$
Rain is followed two days later by rain with probability 7/16 = 0.4375. The zero in $P$ is gone: every entry of $P^2$ is positive, so every kind of weather can follow every other two days later. A nice day is followed two days later by a nice day with probability 0.25, a quarter of the time, although never one day later.
The structure of a chain: communicating classes
The site's link graph is a Markov chain as it stands. The states are the 825 pages, frozen at one commit of the site so that the numbers do not move as pages are added. Every figure for the site below describes the graph at that commit (cce51f7), before this unit was added. From page $i$ with $L(i)$ distinct out-links the surfer moves to each linked page with probability $1/L(i)$, so $p_{ij} = 1/L(i)$ when $i$ links to $j$ and $p_{ij} = 0$ otherwise. A page links to a median of 10 others, and every page links to at least one, so every row sums to 1. Before asking where the surfer ends up, we need to know which pages can reach which.
State $j$ is accessible from $i$, written $i \to j$, if $p_{ij}^{(n)} > 0$ for some $n \ge 0$ (with $n = 0$ allowed, so $i \to i$). By Theorem 1 this means there is a path of positive-probability steps from $i$ to $j$. States $i$ and $j$ communicate, $i \leftrightarrow j$, if each is accessible from the other. Communication is an equivalence relation: it is reflexive by the case $n = 0$, symmetric by definition, and transitive because $p_{ik}^{(a+b)} \ge p_{ij}^{(a)}p_{jk}^{(b)}$ by (2). Its equivalence classes are the communicating classes. A chain is irreducible when it has a single class, that is, when every state is accessible from every other. A class $C$ is closed if no state outside it is accessible from inside: $p_{ij} = 0$ for $i \in C$, $j \notin C$. A state whose class is not closed is transient here; on a finite state space this agrees with the general definition (a state the chain visits only finitely often with probability 1), which the section on absorbing chains proves for the case needed.
The site's chain has 5 communicating classes. The largest class holds 819 pages, almost the whole site. Three pages are classes by themselves: the Information Retrieval collection page, which no page linked to in its text at that commit (readers reached it from the library's index, which is not a page of the graph), and two notes on posts of Anthropic's science blog, each of which links only into the fifth class. That fifth class has three pages, also notes on posts of the science blog: Introducing our Science Blog links to the other two, and each of them links back to it and to nothing else. No link leaves the three, so the class is closed, and it is the only closed class. Links from 16 pages led into it, and 29 links left the largest class. A surfer who only follows links can enter the three pages and can never leave.
A closed class that the surfer enters and never leaves is what PageRank calls a spider trap. That article shows the effect on a small example. The theory below says what the trap does here: it decides the long run of the surfer who never teleports.
Stationary distributions
A distribution that one step of the chain leaves unchanged is the candidate for the long run. A row vector $\pi$ is a stationary distribution of $P$ if its entries are nonnegative, sum to 1, and
$$\pi P = \pi, \quad \text{that is,} \quad \pi_j = \sum_i \pi_i\,p_{ij} \text{ for every } j. \qquad (3)$$
If $X_0$ has distribution $\pi$, then by Theorem 1 every $X_n$ has distribution $\pi P^n = \pi$. For the Land of Oz, $\pi = (2/5, 1/5, 2/5)$: the check for nice weather is $\frac25 \cdot \frac14 + \frac15 \cdot 0 + \frac25 \cdot \frac14 = \frac15$, for rain it is $\frac25 \cdot \frac12 + \frac15 \cdot \frac12 + \frac25 \cdot \frac14 = \frac25$, and for snow $\frac25 \cdot \frac14 + \frac15 \cdot \frac12 + \frac25 \cdot \frac12 = \frac25$. So in the long run it rains on 0.4 of the days and is nice on 0.2 of them, in a sense the ergodic theorem below makes exact.
Three questions follow: does every chain have one, is it unique, and does the chain approach it? Every finite chain has one (Theorem 2); it is unique when every state can reach every other (Theorem 3); and the chain approaches it from every start when, in addition, the chain is aperiodic (Theorem 6).
Existence for every finite chain
Here is the idea. Average the distributions of the first $n$ steps. One more step changes the average only by a term of size $1/n$, so any limit of the averages is unchanged by a step. Finitely many states guarantee that a limit exists along some subsequence.
Theorem 2 (existence). Every stochastic matrix on a finite state space has at least one stationary distribution.
Proof. Fix any initial distribution $\mu$ and let $A_n = \frac1n\sum_{t=0}^{n-1}\mu P^t$, the average of the distributions of $X_0, \ldots, X_{n-1}$. Each $\mu P^t$ is a probability vector by Theorem 1, so $A_n$ is one too: its entries lie in $[0, 1]$ and sum to 1. The averages telescope under one more step:
$$A_nP - A_n = \frac1n\sum_{t=0}^{n-1}\big(\mu P^{t+1} - \mu P^t\big) = \frac1n\big(\mu P^n - \mu\big),$$
and every entry of the right side lies between $-1/n$ and $1/n$. The vectors $A_n$ lie in the bounded set $[0, 1]^m$, so by the Bolzano–Weierstrass theorem some subsequence $A_{n_1}, A_{n_2}, \ldots$ converges to a vector $\pi$. The limit has nonnegative entries summing to 1, since each $A_{n_r}$ does and the conditions are preserved by limits. Matrix multiplication is continuous, so $\pi P - \pi = \lim_r (A_{n_r}P - A_{n_r}) = 0$. $\square$
Levin and Peres (2017, Proposition 1.32) give the same argument. It uses finiteness essentially: on the integers, the simple symmetric random walk has no stationary distribution at all (Norris, 1997, Example 1.7.8).
Uniqueness and positivity for irreducible chains
A reducible chain can have many stationary distributions: if it has two closed classes, a stationary distribution of either one alone, extended by zeros, is stationary for the whole chain, and so is every mixture of the two. Irreducibility rules this out. Here is the idea. A column vector $h$ with $Ph = h$ assigns to each state the average of its values one step later. At a state where $h$ is largest, an average of values can equal the maximum only if all of them equal it. Irreducibility then spreads the maximum to every state, so $h$ is constant. Linear algebra transfers that fact from columns to rows.
Lemma 1 (harmonic functions are constant). Let $P$ be irreducible. If a column vector $h$ satisfies $Ph = h$, then $h$ is constant.
Proof. Let $M = \max_i h_i$, attained at $i_0$. Then $M = h_{i_0} = \sum_j p_{i_0j}h_j$ is an average of values at most $M$ with weights $p_{i_0j}$, so every $j$ with $p_{i_0j} > 0$ has $h_j = M$. Repeating the argument from each such $j$ shows that $h_j = M$ for every $j$ reachable from $i_0$ by a path of positive steps. In an irreducible chain that is every state. $\square$
Theorem 3 (uniqueness and positivity). An irreducible chain on a finite state space has exactly one stationary distribution $\pi$, and $\pi_i > 0$ for every state $i$.
Proof. By Lemma 1 the solutions of $(P - I)h = 0$ are the constant vectors, a space of dimension one, so $P - I$ has rank $m - 1$. A matrix and its transpose have the same rank, so the row vectors $x$ with $x(P - I) = 0$ also form a space of dimension one. Theorem 2 supplies a stationary distribution in it, and every other solution is a multiple of that one; requiring the entries to sum to 1 fixes the multiple. For positivity, (3) iterated gives $\pi = \pi P^n$, so $\pi_j = \sum_i \pi_i\,p_{ij}^{(n)}$ for every $n$. Choose $i$ with $\pi_i > 0$ and, by irreducibility, $n$ with $p_{ij}^{(n)} > 0$; then $\pi_j \ge \pi_i\,p_{ij}^{(n)} > 0$. $\square$
This is the proof of Levin and Peres (2017, Lemma 1.16 and Corollary 1.17). PageRank proves uniqueness for a matrix with every entry positive by a different route, in its section "Why there is exactly one answer". Theorem 3 needs only irreducibility, which allows zeros in $P$.
On the site's chain, the three pages of the closed class form an irreducible chain of their own, with matrix rows $(0, \frac12, \frac12)$ for the introduction page and $(1, 0, 0)$ for each of the other two. Its stationary distribution is $(\frac12, \frac14, \frac14)$: half the time on the introduction, a quarter on each of the others. The section on absorbing chains shows that the whole 825-page chain has exactly one stationary distribution, this one, with zero on the other 822 pages.
Stationary probabilities as return times
Why would the long-run share of a state be connected to how often the chain comes back to it? If the chain returns to $i$ every $m_i$ steps on average, it spends a fraction $1/m_i$ of its time there. The next theorem proves the identity $\pi_i = 1/m_i$ without any appeal to long runs. Write the return time to $i$ as $T_i^+ = \min\{n \ge 1 : X_n = i\}$, with $\min \emptyset = \infty$, and its mean $m_i = E_i[T_i^+]$. The hitting time of a set $A$ is $T_A = \min\{n \ge 0 : X_n \in A\}$, which is 0 when the chain starts in $A$.
Lemma 2 (geometric tails). Let $P$ be irreducible on a finite state space and let $j$ be a state. There are $r \ge 1$ and $\varepsilon > 0$ such that, from every starting state $z$, $P_z(T_j > kr) \le (1 - \varepsilon)^k$ for all $k \ge 0$. Consequently $E_z[(T_j)^p] < \infty$ and $E_z[(T_j^+)^p] < \infty$ for every power $p \ge 1$.
Proof. For each $z$, irreducibility gives a path of positive probability from $z$ to $j$; take $r$ larger than all of their lengths and $\varepsilon$ smaller than all of their probabilities. Then $P_z(T_j \le r) \ge \varepsilon$, that is $P_z(T_j > r) \le 1 - \varepsilon$, for every $z$. The event $\{T_j > (k+1)r\}$ is the event that the path avoids $j$ at times $0, \ldots, kr$ and then again for $r$ more steps. Split the paths by the state $y$ at time $kr$. By (1) the probability of a path is the product of the probability of its part up to time $kr$ and the probability, started at $y$, of its remaining part, so
$$P_z\big(T_j > (k+1)r\big) = \sum_y P_z\big(T_j > kr,\ X_{kr} = y\big)\,P_y(T_j > r) \le (1 - \varepsilon)\,P_z(T_j > kr),$$
and induction on $k$ gives the bound. For the moments, split according to the block of length $r$ in which $T_j$ falls:
$$E_z[(T_j)^p] = \sum_{k \ge 0}E_z\big[(T_j)^p;\ kr < T_j \le (k+1)r\big] \le \sum_{k \ge 0}\big((k+1)r\big)^p\,P_z(T_j > kr) \le \sum_{k \ge 0}\big((k+1)r\big)^p(1 - \varepsilon)^k,$$
a series that converges because the geometric factor $(1-\varepsilon)^k$ shrinks faster than $(k+1)^p$ grows (the ratio test), and $T_j = 0$ contributes nothing. Finally $T_j^+$ is 1 plus the hitting time of $j$ for the chain from $X_1$, so by (1), $E_z[(T_j^+)^p] = \sum_yp_{zy}E_y[(1 + T_j)^p]$, a finite average of finite moments (expand $(1 + T_j)^p$ by the binomial theorem for integer $p$, or bound it by $2^p(1 + T_j^p)$). $\square$
Levin and Peres (2017, Lemma 1.13) prove the finiteness of the means the same way.
Theorem 4 (stationary probabilities are reciprocal mean return times). For an irreducible chain on a finite state space with stationary distribution $\pi$, $\pi_i = 1/m_i$ for every state $i$. In particular every mean return time is finite.
Proof. Fix a state $k$ and let $\gamma_j$ be the expected number of visits to $j$ during one excursion from $k$, counting time 0 and not the return:
$$\gamma_j = E_k\Big[\sum_{n=0}^{T_k^+ - 1}\mathbf{1}\{X_n = j\}\Big] = \sum_{n \ge 0} P_k\big(X_n = j,\ n < T_k^+\big).$$
The two forms agree because every term is nonnegative, so the expectation of the sum is the sum of the expectations. Three facts give the theorem. First, $\gamma_k = 1$: the only visit to $k$ before the return is at time 0. Second, $\sum_j\gamma_j = E_k[T_k^+] = m_k$, finite by Lemma 2, because the visits to all states before the return number exactly $T_k^+$. Third, $\gamma P = \gamma$. For this, the event $\{n \le T_k^+\}$, for $n \ge 1$, is decided by $X_0, \ldots, X_{n-1}$ (the chain has not returned to $k$ at times $1, \ldots, n - 1$), so by (1), $P_k(X_{n-1} = i,\ X_n = j,\ n \le T_k^+) = P_k(X_{n-1} = i,\ n - 1 < T_k^+)\,p_{ij}$. The visits to $j$ at times $1, \ldots, T_k^+$ number the same as at times $0, \ldots, T_k^+ - 1$, since $X_0 = X_{T_k^+} = k$ (both counts include one visit to $k$ if $j = k$ and none otherwise; Lemma 2 makes the return certain). Therefore
$$\gamma_j = \sum_{n \ge 1}P_k\big(X_n = j,\ n \le T_k^+\big) = \sum_i\sum_{n \ge 1}P_k\big(X_{n-1} = i,\ n - 1 < T_k^+\big)\,p_{ij} = \sum_i\gamma_i\,p_{ij},$$
where exchanging the sums is allowed because every term is nonnegative. So $\gamma/m_k$ is a stationary distribution, and by Theorem 3 it is $\pi$. Its $k$-th entry is $\gamma_k/m_k = 1/m_k$. $\square$
This is the argument of Norris (1997, Theorems 1.7.5 and 1.7.7), which also covers infinite chains, where $m_k$ can be infinite; Grinstead and Snell (1997, Theorem 11.15) prove the identity for finite chains by matrix algebra. The proof gives more than the identity: $\gamma_j/m_k = \pi_j$ says that the expected number of visits to $j$ between two visits to $k$ is $\pi_j/\pi_k$.
Example (Land of Oz). The mean time between nice days is $m_N = 1/\pi_N = 5$ days, and between rainy days $1/\pi_R = 2.5$. The section on absorbing chains computes the first figure directly. On the site's closed class, the surfer returns to the introduction page every second click and to each of the other two every fourth click on average, which is $1/\frac12$ and $1/\frac14$.
Periodicity and convergence
Does the chain approach its stationary distribution from every start? Not always. In the site's closed class, a surfer on the introduction page is on it again after every even number of clicks and never after an odd number: $p^{(n)}$ from the introduction to itself is 1, 0, 1, 0, and so on, with no limit, although the stationary probability is $\frac12$. The obstruction is periodicity.
The period of a state $i$ is $d(i) = \gcd\{n \ge 1 : p_{ii}^{(n)} > 0\}$, the greatest common divisor of the lengths of the paths from $i$ back to itself. A state with period 1 is aperiodic, and a chain is aperiodic when all its states are. The introduction page has period 2: every path back to it alternates between it and one of the other two. A chain is regular if some power $P^r$ has every entry positive (Grinstead and Snell, 1997, Definition 11.5). The Land of Oz is regular with $r = 2$.
Lemma 3 (the period is a class property). If $i \leftrightarrow j$, then $d(i) = d(j)$.
Proof. Choose $a, b$ with $p_{ij}^{(a)} > 0$ and $p_{ji}^{(b)} > 0$. By (2), $p_{ii}^{(a+b)} \ge p_{ij}^{(a)}p_{ji}^{(b)} > 0$, so $d(i)$ divides $a + b$. If $p_{jj}^{(n)} > 0$, then $p_{ii}^{(a+n+b)} \ge p_{ij}^{(a)}p_{jj}^{(n)}p_{ji}^{(b)} > 0$, so $d(i)$ divides $a + n + b$ and hence divides $n$. So $d(i)$ divides every element of the set whose greatest common divisor is $d(j)$, and $d(i) \le d(j)$. Exchanging $i$ and $j$ gives the reverse inequality. $\square$
Lemma 4 (sets closed under addition). Let $R$ be a set of positive integers that is closed under addition and has greatest common divisor 1. Then $R$ contains every integer from some point on.
Proof. The greatest common divisors of the finite subsets $\{a_1\}, \{a_1, a_2\}, \ldots$ of an enumeration of $R$ form a nonincreasing sequence of positive integers, so they settle at some value $g$ from some finite subset $\{a_1, \ldots, a_s\}$ on. Then $g$ divides every element of $R$, so $g = 1$. Bézout's identity gives integers $c_1, \ldots, c_s$ with $\sum_l c_la_l = 1$. Let $A$ be the sum of the terms with $c_l > 0$ and $B$ the sum of the absolute values of the others, so $A - B = 1$, and $A$ and $B$ are each either 0 or a sum of elements of $R$, hence in $R$. If $B = 0$, then $1 \in R$ and every positive integer is a sum of ones. Otherwise $B \in R$ and $A = B + 1 \in R$. Take $n \ge B^2$ and divide: $n = qB + s$ with $0 \le s < B$. Since $n \ge B^2$, $q \ge B > s$. Then $n = qB + s(A - B) = (q - s)B + sA$ with $q - s \ge 1$, a sum of elements of $R$. $\square$
This is a form of the number-theoretic fact that Levin and Peres (2017, Lemma 1.30) state and use for the next theorem.
Theorem 5 (regular = irreducible and aperiodic). A chain on a finite state space is regular if and only if it is irreducible and aperiodic. In that case there is $r_0$ such that $P^r$ has every entry positive for every $r \ge r_0$.
Proof. Suppose $P^r$ has every entry positive. Then the chain is irreducible. Also $P^{r+1} = P\,P^r$ has every entry positive: entry $(i, j)$ is $\sum_k p_{ik}(P^r)_{kj}$, and some $p_{ik} > 0$ because row $i$ sums to 1. So $p_{ii}^{(r)} > 0$ and $p_{ii}^{(r+1)} > 0$, and $d(i)$ divides two consecutive integers, hence is 1.
Conversely, suppose the chain is irreducible and aperiodic. For each state $i$, the set $R_i = \{n \ge 1: p_{ii}^{(n)} > 0\}$ is closed under addition, because $p_{ii}^{(a+b)} \ge p_{ii}^{(a)}p_{ii}^{(b)}$ by (2), and has greatest common divisor $d(i) = 1$. By Lemma 4 it contains every $n \ge N_i$. For states $i$ and $j$ choose $a_{ij}$ with $p_{ij}^{(a_{ij})} > 0$; then for $n \ge N_i + a_{ij}$, $p_{ij}^{(n)} \ge p_{ii}^{(n - a_{ij})}\,p_{ij}^{(a_{ij})} > 0$. The largest of the finitely many thresholds $N_i + a_{ij}$ is $r_0$. $\square$
Levin and Peres (2017, Proposition 1.7) prove the second half the same way. A single loop $p_{ii} > 0$ makes an irreducible chain aperiodic, since then $1 \in R_i$. That is why the "lazy" version of a chain, which stays put with probability one half at each step, is used in many proofs, and why PageRank's teleportation, which can land on the current page, removes every period.
Convergence at a geometric rate
How far is the distribution of $X_n$ from $\pi$, and how fast does the distance shrink? For an irreducible aperiodic chain it shrinks at least geometrically from every start (Theorem 6 below). Distances between distributions are measured in total variation,
$$\lVert \mu - \nu \rVert_{\mathrm{TV}} = \frac12\sum_i\lvert\mu_i - \nu_i\rvert = \max_{A \subseteq S}\lvert\mu(A) - \nu(A)\rvert,$$
the largest difference between the probabilities that the two distributions give to any event. The two expressions are equal because the maximum is attained by the set $A$ of states where $\mu_i > \nu_i$, and the positive and negative parts of $\mu - \nu$ have the same total (Levin and Peres, 2017, Proposition 4.2). The worst-case distance after $n$ steps is $d(n) = \max_i\lVert P^n(i, \cdot) - \pi\rVert_{\mathrm{TV}}$, where $P^n(i, \cdot)$ is row $i$ of $P^n$.
Here is the idea of the proof. One step of a chain moves two distributions closer together unless some pair of rows of $P$ have nothing in common. The contraction coefficient of a stochastic matrix $M$ measures how far apart its rows can be:
$$\delta(M) = \max_{i, k}\lVert M(i, \cdot) - M(k, \cdot)\rVert_{\mathrm{TV}}.$$
It lies between 0 and 1, and it is less than 1 exactly when every two rows put positive probability on some common state.
Lemma 5 (contraction). For any probability vectors $\mu$ and $\nu$ and any stochastic matrix $M$, $\lVert\mu M - \nu M\rVert_{\mathrm{TV}} \le \delta(M)\,\lVert\mu - \nu\rVert_{\mathrm{TV}}$. Consequently $\delta(MM') \le \delta(M)\,\delta(M')$.
Proof. Let $x = \mu - \nu$ and write it as $x = x^+ - x^-$ with $x_i^+ = \max(x_i, 0)$ and $x_i^- = \max(-x_i, 0)$. Since $x$ sums to 0, both parts have the same total $s = \lVert\mu - \nu\rVert_{\mathrm{TV}}$. If $s = 0$ there is nothing to prove. Otherwise
$$xM = \sum_i x_i^+M(i, \cdot) - \sum_k x_k^-M(k, \cdot) = \frac1s\sum_{i, k}x_i^+x_k^-\big(M(i, \cdot) - M(k, \cdot)\big),$$
because $\sum_k x_k^- = \sum_i x_i^+ = s$. By the triangle inequality, $\frac12\sum_j\lvert(xM)_j\rvert \le \frac1s\sum_{i,k}x_i^+x_k^-\,\lVert M(i, \cdot) - M(k, \cdot)\rVert_{\mathrm{TV}} \le \frac1s\,s^2\,\delta(M) = s\,\delta(M)$. For the product, rows $i$ and $k$ of $MM'$ are $M(i, \cdot)M'$ and $M(k, \cdot)M'$, whose distance is at most $\delta(M')\lVert M(i, \cdot) - M(k, \cdot)\rVert_{\mathrm{TV}} \le \delta(M')\,\delta(M)$. $\square$
Theorem 6 (convergence to stationarity). Let $P$ be a stochastic matrix on a finite state space with a stationary distribution $\pi$, and let $r \ge 1$ be such that $\delta(P^r) < 1$. For an irreducible aperiodic chain such an $r$ exists: by Theorem 5 some $P^r$ has every entry positive, and then any two of its rows overlap. Then, for every initial distribution $\mu$ and every $n$,
$$\lVert\mu P^n - \pi\rVert_{\mathrm{TV}} \le \delta(P^r)^{\lfloor n/r \rfloor}.$$
In particular $P^n \to \mathbf{1}\pi$, the matrix whose rows all equal $\pi$, at a geometric rate, and $d(n)$ never increases.
Proof. If $P^r$ has every entry positive, every two of its rows are positive at every state, so they overlap and $\delta(P^r) < 1$; this justifies the remark in the statement. Since $\pi = \pi P^n$, Lemma 5 applied to $\mu$ and $\pi$ gives $\lVert\mu P^n - \pi\rVert_{\mathrm{TV}} = \lVert\mu P^n - \pi P^n\rVert_{\mathrm{TV}}$. Write $n = qr + s$ with $q = \lfloor n/r\rfloor$ and $0 \le s < r$, and apply Lemma 5 $q$ times with $M = P^r$ and $s$ times with $M = P$, for which $\delta(P) \le 1$: the distance is at most $\delta(P^r)^q\lVert\mu - \pi\rVert_{\mathrm{TV}} \le \delta(P^r)^q$. The same lemma with $M = P$ shows that one more step never increases the distance, so $d(n)$ is nonincreasing. $\square$
Levin and Peres (2017, Theorem 4.9) prove the convergence theorem by splitting $P^r$ into a multiple of $\mathbf{1}\pi$ and a remainder, the same device Latent Dirichlet Allocation uses for a matrix with all entries positive. The contraction coefficient is a form of the same idea that avoids naming $\pi$ in advance; it also gives a second proof of uniqueness, since two stationary distributions would be at a fixed positive distance that the contraction must shrink.
Example (how sharp the bound is). The Land of Oz has a zero in $P$, yet every two of its rows overlap: each pair of rows is at total variation distance exactly $\frac14$, so $\delta(P) = \frac14 < 1$ and Theorem 6 with $r = 1$ gives $d(n) \le (\frac14)^n$. The exact distance, computed in fractions, is $d(n) = \frac15(\frac14)^{n-1}$: $d(1) = 0.2$, attained from a nice day, and $d(2) = 0.05$. The bound has the right rate and is off by the constant factor $\frac45$. The rate is the size of the second-largest eigenvalue: the eigenvalues of $P$ are $1$, $\frac14$ and $-\frac14$ (their sum is the trace, 1, and their product the determinant, $-\frac1{16}$). For a matrix with distinct eigenvalues PageRank derives, in its section "How fast it converges", that the error of power iteration eventually shrinks by the modulus of the second eigenvalue at each step; Levin and Peres (2017, chapter 12) treat the general case.
Example (a periodic chain). In the site's closed class, $P^n$ does not converge: $P^n$ from the introduction page alternates between the two halves of the class. Theorem 6 does not apply because the class has period 2. What does converge is the average $\frac1n\sum_{t<n}P^t$, which by the proof of Theorem 2 and the uniqueness of Theorem 3 has every row equal to $(\frac12, \frac14, \frac14)$. Fractions of time behave well even when probabilities at fixed times do not, which is the content of the next section.
The ergodic theorem: time averages along one path
A stationary distribution is a statement about probabilities over many imagined runs. A reader of the site runs once. Does the fraction of time one path spends at a state approach its stationary probability? Here is the idea. Cut the path at its visits to state $i$. Each piece between two visits, an excursion, starts afresh from $i$, so the excursions are independent and identically distributed with mean length $m_i$. By the strong law of large numbers the first $k$ excursions take about $km_i$ steps, so $n$ steps contain about $n/m_i$ visits, and $1/m_i = \pi_i$ by Theorem 4.
Lemma 6 (the chain starts afresh at a visit). Let $j$ be a state and $T = T_j$ its hitting time. For every path $x_0, \ldots, x_t$ that reaches $j$ for the first time at $t$, and every path $j, y_1, \ldots, y_l$,
$$P\big(X_0 = x_0, \ldots, X_t = x_t,\ X_{t+1} = y_1, \ldots, X_{t+l} = y_l\big) = P\big(X_0 = x_0, \ldots, X_t = x_t\big)\,P_j\big(X_1 = y_1, \ldots, X_l = y_l\big).$$
In words: given that $T = t$ and given the path up to $T$, the path after $T$ is a chain started at $j$. In particular, for a chain started at $i$, the successive excursions from $i$ are independent and identically distributed.
Proof. By (1) the left side is $\mu_{x_0}$ times the transition probabilities along the whole path. They split into those up to time $t$, whose product with $\mu_{x_0}$ is the first factor, and those from $x_t = j$ onward, whose product is the second factor by (1) for the chain started at $j$. For excursions, a path that consists of excursions $e_1, \ldots, e_r$ from $i$ (each a path from $i$ back to $i$ with no visit to $i$ in between) has, by the same splitting, probability $P_i(\text{first excursion} = e_1)\cdots P_i(\text{first excursion} = e_r)$. Lemma 2 makes every excursion finite with probability 1, so these probabilities, summed over all finite excursions, give 1. Hence the $r$-th excursion has the same distribution as the first, and the first $r$ are independent. $\square$
Theorem 7 (the ergodic theorem). Let $P$ be irreducible on a finite state space, with stationary distribution $\pi$, and let the chain start from any initial distribution. Write $V_i(n) = \sum_{t=0}^{n-1}\mathbf{1}\{X_t = i\}$ for the number of visits to $i$ before time $n$. Then, with probability 1,
$$\frac{V_i(n)}{n} \to \pi_i = \frac{1}{m_i}, \qquad \text{and} \qquad \frac1n\sum_{t=0}^{n-1}f(X_t) \to \sum_i\pi_i\,f(i)$$
for every function $f$ on the states.
Proof. Start at $i$. Let $L_1, L_2, \ldots$ be the lengths of the successive excursions from $i$. By Lemma 6 they are independent and identically distributed, with mean $m_i$, and by Lemma 2 with a finite fourth moment. The strong law of large numbers under a finite fourth moment (The Laws of Large Numbers, section "The strong law under a finite fourth moment") gives $(L_1 + \cdots + L_k)/k \to m_i$ with probability 1. The $V = V_i(n)$ visits before time $n$ begin $V$ excursions, of which the first $V - 1$ are complete before time $n$ and the $V$-th ends at or after time $n$:
$$L_1 + \cdots + L_{V - 1} \le n - 1, \qquad L_1 + \cdots + L_V \ge n.$$
Each excursion is finite, so $V_i(n) \to \infty$ as $n \to \infty$. Dividing both inequalities by $V$ and letting $n \to \infty$, both outer sides tend to $m_i$, so $n/V_i(n) \to m_i$, and $V_i(n)/n \to 1/m_i$, which is $\pi_i$ by Theorem 4.
From another start, the chain hits $i$ at a time $T_i$ that is finite with probability 1 (Lemma 2). By Lemma 6, applied to the finite paths that make up the first $k$ excursions after $T_i$ for every $k$, the lengths of the excursions from $i$ after $T_i$ are independent of $T_i$ and of one another, each with the law of $T_i^+$ under $P_i$; independence of a sequence is a statement about its finite subfamilies, so the strong law applies to them. The argument above, with time counted from $T_i$, gives the same limit. The $T_i$ steps before it change $V_i(n)$ by at most $T_i$, and $T_i/n \to 0$. Finally $\frac1n\sum_{t<n}f(X_t) = \sum_i f(i)\,V_i(n)/n$, a finite sum of terms that each converge with probability 1. $\square$
Norris (1997, Theorem 1.10.2) proves the theorem this way for chains on countable spaces; Levin and Peres (2017, Theorem C.1) state and prove it for finite chains; Grinstead and Snell (1997, Theorem 11.12) state, without proof, the weaker result that the fraction converges in probability. The theorem needs no aperiodicity: the surfer caught in the site's closed class spends half of its clicks on the introduction page in the long run, although the probability of being there at a given click alternates between 0 and 1.
How variable is a time average for finite $n$? Successive states are dependent, so the variance of $\frac1n\sum f(X_t)$ involves the autocovariances of $f(X_t)$ at every lag. The variance of the mean of a stationary series is derived in Resampling Dependent and Clustered Data (Theorem 1) and used for MCMC averages in Markov Chain Monte Carlo (section "Measuring the error: autocorrelation and effective sample size"); Autocorrelation and Stationarity treats it in general. Grinstead and Snell (1997, Theorem 11.17) state a central limit theorem for the number of visits of an ergodic chain, which this article cites and does not prove.
Absorbing chains: how long until the surfer is caught
Back to the surfer who never teleports. From most pages, the closed class is far away in clicks. How long does it take to fall in, and is it certain to? It is certain, and from almost every page it takes about 30,000 clicks on average. Treat the three pages of the closed class as one place the surfer cannot leave. The question is then about an absorbing chain.
A state $a$ is absorbing if $p_{aa} = 1$. A chain is absorbing if it has at least one absorbing state and every state can reach one; the non-absorbing states are then transient. Order the $t$ transient states first and the $s$ absorbing states last. The transition matrix takes the canonical form
$$P = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix},$$
where $Q$ ($t \times t$) holds the moves among transient states, $R$ ($t \times s$) the moves from transient to absorbing states, $0$ is a block of zeros and $I$ the $s \times s$ identity. The fundamental matrix is $N = (I - Q)^{-1}$; the next theorem shows that it exists.
Theorem 8 (absorbing chains). In an absorbing chain on a finite state space:
- $Q^n \to 0$ at a geometric rate, so absorption happens with probability 1;
- $I - Q$ is invertible and $N = (I - Q)^{-1} = I + Q + Q^2 + \cdots$; its entry $N_{ij}$ is the expected number of visits to the transient state $j$ for the chain started at the transient state $i$, counting time 0;
- the expected number of steps before absorption from transient state $i$ is the $i$-th entry of $\mathbf{t} = N\mathbf{1}$;
- the probability of absorption in the absorbing state $a$ from transient state $i$ is the entry $(i, a)$ of $B = NR$.
The vectors $\mathbf{t}$ and $B$ are also the unique solutions of the first-step equations $\mathbf{t} = \mathbf{1} + Q\mathbf{t}$ and $B = R + QB$.
Proof. (1) By (1) and Theorem 1, $(Q^n)_{ij}$ is the sum of the path probabilities of the paths of $n$ steps from $i$ to $j$ that stay among transient states, so $\sum_j(Q^n)_{ij} = P_i(\text{not absorbed by time } n)$. The proof of Lemma 2 applies with the set of absorbing states in place of $j$: from every transient state some absorbing state is reachable, so there are $r$ and $\varepsilon > 0$ with $P_i(\text{not absorbed by time } kr) \le (1-\varepsilon)^k$. Every entry of $Q^n$ is at most this.
(2) If $(I - Q)x = 0$ then $x = Qx = Q^nx \to 0$, so $x = 0$ and $I - Q$ is invertible. The partial sums satisfy $(I - Q)(I + Q + \cdots + Q^{K-1}) = I - Q^K \to I$, and the series converges entrywise because its terms decrease geometrically; multiplying by $N$ gives $\sum_{n \ge 0}Q^n = N$. The number of visits to $j$ is $\sum_{n \ge 0}\mathbf{1}\{X_n = j\}$, and its expectation from $i$ is $\sum_n (Q^n)_{ij} = N_{ij}$, since a visit to a transient $j$ at time $n$ is a path that has stayed among transient states.
(3) The number of steps before absorption is the total number of visits to transient states, $\sum_j\sum_n\mathbf{1}\{X_n = j\}$, with expectation $\sum_jN_{ij}$.
(4) Absorption in $a$ at time $n + 1$ means $n$ steps among transient states to some $k$ and then a step from $k$ to $a$, with probability $\sum_k(Q^n)_{ik}R_{ka}$. Summing over $n$ gives $(NR)_{ia}$. For the equations, conditioning on the first step gives $t_i = 1 + \sum_kQ_{ik}t_k$ and $B_{ia} = R_{ia} + \sum_kQ_{ik}B_{ka}$, and $I - Q$ is invertible, so these linear systems have exactly one solution each. $\square$
These are Theorems 11.3 to 11.6 of Grinstead and Snell (1997), proved there in the same way. Random Walks and Martingales solves the gambler's ruin by the first-step equations and again by optional stopping. The gambler's fortune there is a finite chain on $\{0, 1, \ldots, b\}$ with the two ends absorbing, so Theorem 8 applies to it directly.
Corollary 1 (stationary mass sits on closed classes). In a finite chain, every stationary distribution gives probability 0 to every state outside the closed classes. If there is exactly one closed class, the stationary distribution is unique: that of the class, extended by zeros.
Proof. First, from every state some closed class can be reached. The relation "class $A$ leads to class $B$" between different communicating classes has no cycles (classes on a cycle would communicate and be one class), so following it from any class must stop, after finitely many classes, at a class that leads nowhere else, which is closed. Let $\mathcal{T}$ be the states outside the closed classes and $Q$ the block of $P$ on them. No state of a closed class leads into $\mathcal{T}$, so for $j \in \mathcal{T}$ the equation $\pi_j = \sum_i\pi_ip_{ij}$ has nonzero terms only from $i \in \mathcal{T}$: the row vector $\pi_{\mathcal{T}}$ satisfies $\pi_{\mathcal{T}} = \pi_{\mathcal{T}}Q = \pi_{\mathcal{T}}Q^n$. Making every state of the closed classes absorbing does not change $Q$, so by Theorem 8, $Q^n \to 0$ and $\pi_{\mathcal{T}} = 0$. With one closed class, $\pi$ restricted to it is a stationary distribution of the class, an irreducible chain, which is unique by Theorem 3. $\square$
Example (the first nice day in Oz). Make the nice day absorbing. The transient states are rain and snow, with $Q = \begin{pmatrix} 1/2 & 1/4 \\ 1/4 & 1/2\end{pmatrix}$, so $I - Q$ has determinant $\frac14 - \frac1{16} = \frac3{16}$ and
$$N = \frac{16}{3}\begin{pmatrix} 1/2 & 1/4 \\ 1/4 & 1/2\end{pmatrix} = \begin{pmatrix} 8/3 & 4/3 \\ 4/3 & 8/3 \end{pmatrix}, \qquad \mathbf{t} = N\mathbf{1} = \begin{pmatrix} 4 \\ 4 \end{pmatrix}.$$
From a rainy or a snowy day the first nice day comes after 4 days on average. A nice day is followed by rain or snow, so the mean return time to a nice day is $1 + \frac12 \cdot 4 + \frac12 \cdot 4 = 5$, which is $1/\pi_N$ as Theorem 4 says.
The surfer, caught. On the site, make the three pages of the closed class absorbing. The other 822 pages are transient: every one of them can reach the class, so Theorem 8 applies. The script inverts the $822 \times 822$ matrix $I - Q$ and checks that $\mathbf{t} = \mathbf{1} + Q\mathbf{t}$ and that the absorption probabilities sum to 1. The expected number of clicks before the surfer is caught has median 29,632 over the transient pages. From the Statistics collection page it is 29,664. The longest wait, 30,993 clicks, starts from the algebra course's page on polynomial arithmetic. The shortest is 1 click, from a science-blog note that links only into the trap. The waits barely depend on the start: almost all of the time is spent wandering the 819-page class, which the surfer leaves only through 29 links. From the statistics page, the first page of the trap to be reached is the introduction with probability 0.533. By Corollary 1, the stationary distribution of the whole 825-page chain is unique and lives on the three pages, $(\frac12, \frac14, \frac14)$, with zero everywhere else. A long run of link-following on this site ends in the science-blog notes, however it starts.
Example (a common misreading: a stationary distribution says where the chain is "most of the time"). The no-teleportation surfer has a unique stationary distribution, zero on 822 pages, yet the surfer spends its first thirty thousand clicks or so on exactly those pages. The stationary distribution describes the long run, and on this site the long run starts late. How fast the long run arrives is a separate question from what it is, and it is the subject of the next example and of the section on reversibility.
The surfer with teleportation, and how fast it mixes
PageRank fixes the trap by teleportation: at each click, with probability $1 - d = 0.15$ the surfer jumps to a page chosen uniformly from all 825 instead of following a link. The resulting matrix $G = dP + \frac{1-d}{825}\mathbf{1}\mathbf{1}^{\mathsf T}$ has every entry positive, so it is regular, with a unique stationary distribution, PageRank, by Theorem 3, and convergence by Theorem 6.
The pages with the largest PageRank are:
The first row is the trap seen through teleportation. Teleportation lets the surfer out, but every visit to the three pages bounces between them until a jump, so they collect 0.016 of the long-run time between them, 4.3 times their uniform share of 3/825. The next four are pages with many in-links: the information retrieval course's pages on significance testing and on relevance judgments (linked from 56 and 39 pages), the library's article on probability inequalities (47) and the statistics course's page on the chi-squared and t distributions (45). The Statistics collection page itself has PageRank 0.0003, about a fifth (0.22) of the uniform share $1/825 = 0.0012$ and close to the $0.15/825 = 0.0002$ that teleportation alone gives every page, because at that commit only 1 page linked to it in its text: readers reached it from menus.
The three pages of the trap have since been given links to the rest of the library; the numbers here describe the graph as it was at commit cce51f7.
How fast. The contraction coefficient of $G$ is at most $d = 0.85$: every two rows of $G$ share the teleportation term $\frac{1-d}{825}$ at every page. Here two pages share no out-link, so $\delta(P) = 1$ and $\delta(G) = 0.85$ exactly. Theorem 6 with $r = 1$ gives $d(n) \le 0.85^n$ from every start, the bound PageRank proves in its section "How fast it converges". The exact worst-case distances from stationarity are:
| Clicks $n$ | 1 | 5 | 10 | 20 | 40 |
|---|---|---|---|---|---|
| $d(n)$ | 0.8496 | 0.4395 | 0.1949 | 0.0384 | 0.001486 |
The bound is nearly attained: $0.85^{20} = 0.0388$ against an exact 0.0384. The trap shows that the rate cannot be improved. Its period 2 gives $P$ the eigenvalue $-1$, with left eigenvector $(1, -\frac12, -\frac12)$ on the three pages and 0 elsewhere. That vector sums to 0, so the teleportation term removes nothing from it, and $G$ has the eigenvalue $-0.85$ exactly. So no bound $C\rho^n$ with $\rho < 0.85$ can hold, and the bound $0.85^n$ is off at most by a constant factor; here, from the introduction page, which is the worst start at $n = 20$, the factor is 0.99. (The slow leak out of the large class and the algebra cluster described below give $G$ the eigenvalues 0.84997 and 0.84922 as well, so even without the trap's period the rate would be about 0.85.) Twenty clicks bring every starting page within 0.04 of PageRank in total variation.
Without teleportation, mixing is slow even inside the large class. Delete the 29 links that leave the 819-page class, so that the surfer stays in it. That chain is irreducible, and it is aperiodic (the script finds cycles of coprime lengths), so Theorem 6 applies, but its second-largest eigenvalue is 0.99909. The time scale $1/(1 - \lambda_2)$ is 1,096 clicks; it is called the relaxation time by analogy with reversible chains, where Theorem 11 below gives it a meaning, and here it is meaningful because $\lambda_2$ is real and dominates the other eigenvalues. The exact worst-case distance is still 0.66 after 256 clicks, 0.33 after 1,024 and 0.020 after 4,096. The right eigenvector of the second eigenvalue, the function of the state that decays most slowly, identifies the bottleneck: split by its sign, it separates the 45 pages of the course on abstract algebra (modular arithmetic, Fermat's little theorem, RSA, rings and fields) from everything else. Only 1 link leads out of them, from the page on symmetric groups to an evolutionary-computing page on the eight-queens puzzle, and 4 lead in, yet in the long run the surfer spends 0.170 of the time there. A surfer who enters the algebra pages stays for many clicks, and one outside takes many clicks to find the way in. The slow approach to stationarity is a statement about the graph: a well-linked cluster joined to the rest by a few links.
The ergodic theorem, observed. The script simulates the surfer with teleportation for 100,000 clicks from the statistics page, with 30 seeds. The fraction of clicks spent on the introduction page, whose PageRank is 0.0078, has median 0.0079 (interquartile range 0.0073 to 0.0083). The largest difference, over all 825 pages, between a page's fraction of clicks and its PageRank has median 0.0007 (0.0006 to 0.0008). The mean time between visits to the introduction page has median 125.6 clicks (118.5 to 135.2), against $1/\pi = 127.6$ from Theorem 4. These are observations of one simulation, and they agree with Theorems 4 and 7 to within the variation between seeds.
Reversibility and the random walk on a graph
Some chains look the same run backward. Consider a stationary chain filmed and played in reverse. When are the two films indistinguishable? Here is the idea: for every pair of states, the flow of probability from the first to the second must equal the flow back.
A distribution $\pi$ satisfies detailed balance for $P$ if $\pi_i\,p_{ij} = \pi_j\,p_{ji}$ for all states $i, j$. The chain is reversible with respect to $\pi$ if, started from $\pi$, every path has the same probability as its reversal: $P_\pi(X_0 = i_0, \ldots, X_n = i_n) = P_\pi(X_0 = i_n, \ldots, X_n = i_0)$.
Theorem 9 (detailed balance). If $\pi$ satisfies detailed balance for $P$, then $\pi$ is stationary and the chain started from $\pi$ is reversible. Conversely, a chain that is reversible with respect to a distribution satisfies detailed balance for it.
Proof. Summing $\pi_ip_{ij} = \pi_jp_{ji}$ over $i$ gives $\sum_i\pi_ip_{ij} = \pi_j\sum_ip_{ji} = \pi_j$, which is (3). For reversibility, by (1) the path probability is $\pi_{i_0}p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{n-1}i_n}$. Apply detailed balance to the first factor pair, $\pi_{i_0}p_{i_0i_1} = \pi_{i_1}p_{i_1i_0}$, then to $\pi_{i_1}p_{i_1i_2} = \pi_{i_2}p_{i_2i_1}$, and so on along the path. After $n$ applications the product is $\pi_{i_n}p_{i_ni_{n-1}}\cdots p_{i_1i_0}$, the probability of the reversed path. Conversely, reversibility for paths of one step is $\pi_ip_{ij} = \pi_jp_{ji}$. $\square$
Markov Chain Monte Carlo proves the first part on continuous spaces (its Theorem 1), where it is the reason the Metropolis–Hastings sampler has the target as its stationary distribution, and gives a systematic-scan Gibbs sampler as an example of a stationary chain that is not reversible. Levin and Peres (2017, Propositions 1.20 and 1.23) state the finite case.
The site's surfer is not reversible: a link from $i$ to $j$ without one back gives $p_{ij} > 0 = p_{ji}$, which detailed balance forbids for positive $\pi$. Ignore the directions of the links and the result is reversible. On an undirected graph, the simple random walk moves from a vertex to one of its neighbors chosen uniformly.
Theorem 10 (random walk on a graph). On a finite connected undirected graph with $E$ edges, the simple random walk is reversible with respect to $\pi_i = \deg(i)/2E$, which is therefore its unique stationary distribution.
Proof. For neighbors $i$ and $j$, $\pi_i\,p_{ij} = \frac{\deg(i)}{2E}\cdot\frac{1}{\deg(i)} = \frac{1}{2E}$, which is symmetric in $i$ and $j$; for non-neighbors both sides are 0. The degrees sum to $2E$, so $\pi$ is a distribution. Theorem 9 makes it stationary, and the walk on a connected graph is irreducible, so Theorem 3 makes it unique. $\square$
The undirected link graph of the site has 7,267 edges. Its stationary distribution needs no computation: a page's long-run share is its number of neighbors divided by $2 \times 7{,}267$. The largest degree, 324, belongs to the page that indexes the notes on Anthropic's research.
A bound from the second eigenvalue
Reversibility buys a convergence bound from eigenvalues. Here is the idea. Detailed balance makes $P$ symmetric after rescaling, so it has real eigenvalues and an orthonormal basis of eigenvectors. The distance from stationarity is then a sum of eigenvalue powers, all of which except the first decay at least as fast as the largest of their sizes.
Theorem 11 (spectral bound). Let $P$ be irreducible on a finite state space and reversible with respect to $\pi$. Its eigenvalues are real, $1 = \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_m \ge -1$, with $\lambda_2 < 1$. Let $\lambda_* = \max(\lambda_2, \lvert\lambda_m\rvert)$. Then for every state $i$ and every $n$,
$$\lVert P^n(i, \cdot) - \pi\rVert_{\mathrm{TV}} \le \frac12\sqrt{\frac{1 - \pi_i}{\pi_i}}\;\lambda_*^n.$$
Proof. Let $D$ be the diagonal matrix of the $\pi_i$, all positive by Theorem 3, and $A = D^{1/2}PD^{-1/2}$, with entries $A_{ij} = \pi_ip_{ij}/\sqrt{\pi_i\pi_j}$. Detailed balance makes $A$ symmetric. By the real spectral theorem (Covariance Matrices and Quadratic Forms, Theorem 2, cited there), $A = \sum_k\lambda_ku_ku_k^{\mathsf T}$ with real $\lambda_k$ and orthonormal column vectors $u_k$. $A$ and $P$ are similar, so they have the same eigenvalues. The vector $u_1$ with entries $\sqrt{\pi_j}$ has unit length and $Au_1 = D^{1/2}P\mathbf{1} = u_1$, so it is an eigenvector for $\lambda_1 = 1$. Every eigenvalue has modulus at most 1, because $\lVert xP\rVert_1 \le \lVert x\rVert_1$ for every row vector $x$. The eigenvalue 1 is simple: its right eigenvectors for $P$ are constant by Lemma 1, and for a symmetric matrix the multiplicity of an eigenvalue equals the dimension of its eigenspace. So $\lambda_2 < 1$.
Since $P^n = D^{-1/2}A^nD^{1/2}$,
$$P^n(i, j) = \sqrt{\frac{\pi_j}{\pi_i}}\sum_k\lambda_k^nu_k(i)\,u_k(j) = \pi_j + \sqrt{\frac{\pi_j}{\pi_i}}\sum_{k \ge 2}\lambda_k^nu_k(i)\,u_k(j),$$
the term $k = 1$ being $\sqrt{\pi_j/\pi_i}\sqrt{\pi_i}\sqrt{\pi_j} = \pi_j$. Write $c_j = \sum_{k \ge 2}\lambda_k^nu_k(i)u_k(j)$. By the Cauchy–Schwarz inequality (Probability Inequalities: Markov, Chebyshev, Jensen and Cauchy–Schwarz, its finite vector form),
$$2\lVert P^n(i, \cdot) - \pi\rVert_{\mathrm{TV}} = \frac{1}{\sqrt{\pi_i}}\sum_j\sqrt{\pi_j}\,\lvert c_j\rvert \le \frac{1}{\sqrt{\pi_i}}\Big(\sum_j\pi_j\Big)^{1/2}\Big(\sum_jc_j^2\Big)^{1/2}.$$
The $u_k$ are orthonormal, so $\sum_jc_j^2 = \sum_{k \ge 2}\lambda_k^{2n}u_k(i)^2 \le \lambda_*^{2n}\sum_{k \ge 2}u_k(i)^2$. The matrix with columns $u_k$ is orthogonal, so its rows have unit length too, and $\sum_{k \ge 2}u_k(i)^2 = 1 - u_1(i)^2 = 1 - \pi_i$. Putting the pieces together gives the bound. $\square$
Levin and Peres (2017) give the spectral decomposition as Lemma 12.2, and in Lemma 12.18(i) the inequality $4\lVert P^t(x, \cdot) - \pi\rVert_{\mathrm{TV}}^2 \le \sum_{j \ge 2}f_j(x)^2\lambda_j^{2t}$ for orthonormal eigenfunctions $f_j$ in their inner product weighted by $\pi$, from which the bound above follows because $\sum_{j \ge 2}f_j(x)^2 = (1 - \pi(x))/\pi(x)$. (The displayed relation is an inequality; the equality inside it is in the $L^2$ norm weighted by $\pi$.) The bound is useful only when $\lambda_* < 1$, which fails exactly when $-1$ is an eigenvalue; for an irreducible chain that can happen only if the chain is periodic (the same book, Lemma 12.1(iii), cited here). A lazy chain, $\frac12(I + P)$, has all eigenvalues in $[0, 1]$ and avoids the problem.
On the site's undirected graph. The eigenvalues are $\lambda_2 = 0.9955$ and $\lambda_m = -0.468$, so $\lambda_* = \lambda_2$, and the bound's worst case starts from the page with the smallest share. After 256 steps the exact worst-case distance is 0.300 and the bound is 13.341, which says nothing. After 1,024 steps the distance is 0.009 and the bound 0.409. The bound has the right rate but a large constant, $\frac12\sqrt{(1-\pi_i)/\pi_i}$, which is 42.6 for a page with only two neighbors. Ignoring link directions shortens the time scale $1/(1 - \lambda_2)$ from the directed chain's 1,096 steps to 221, here a relaxation time in the proper sense since the walk is reversible. That is consistent with the algebra pages now being left along every link that touches them: the sign of the second eigenvector still separates the 45 algebra pages (with two pages next to them), but they now have 4 boundary edges instead of 1 exit link.
What is proved here, what is cited, what the experiment shows
Proved here, for finite state spaces and with sums only: the Chapman–Kolmogorov equations (Theorem 1); existence of a stationary distribution for every chain (Theorem 2); constancy of harmonic functions (Lemma 1), and uniqueness and positivity for irreducible chains (Theorem 3); geometric tails of hitting times (Lemma 2); $\pi_i = 1/m_i$ (Theorem 4); periodicity as a class property (Lemma 3), the number-theoretic lemma (Lemma 4), and regular = irreducible and aperiodic (Theorem 5); the contraction lemma (Lemma 5) and convergence at a geometric rate (Theorem 6); the chain starting afresh at a hitting time and the independence of excursions (Lemma 6), and the ergodic theorem (Theorem 7), given the strong law under a finite fourth moment proved in The Laws of Large Numbers; the fundamental matrix of an absorbing chain (Theorem 8) and the vanishing of stationary mass off the closed classes (Corollary 1); detailed balance and reversibility (Theorem 9); the random walk on a graph (Theorem 10); and the spectral bound for reversible chains (Theorem 11), given the real spectral theorem.
Cited. The real spectral theorem (through Covariance Matrices and Quadratic Forms); Bolzano–Weierstrass and Bézout as standard facts of analysis and number theory; the absence of the eigenvalue $-1$ for irreducible aperiodic chains (Levin and Peres, 2017, Lemma 12.1); the central limit theorem for Markov chains (Grinstead and Snell, 1997, Theorem 11.17); everything about chains on infinite or continuous state spaces (Norris, 1997; Roberts and Rosenthal (2004), cited in Markov Chain Monte Carlo). The Land of Oz chain is Grinstead and Snell's Example 11.1.
What the computations show. The Land of Oz in exact fractions: $P^2$, $\pi$, mean return and first-passage times, and the exact distance $d(n) = \frac15(\frac14)^{n-1}$. The site's link graph at one commit: its five classes, the closed class of three pages, the expected 29,632 clicks (median) before the link-following surfer is caught, the slow mixing inside the large class caused by 45 algebra pages, PageRank and its exact distances from stationarity against the bound $0.85^n$, and the undirected walk's eigenvalues against Theorem 11. The simulation over 30 seeds shows time fractions and return times agreeing with Theorems 4 and 7; these are observations of that simulation.
Worked problems
These problems were written for this article, on the chains used above and on small exact cases; each answer is computed in exact arithmetic by the article's script.
Problem 1 (the Land of Oz). Find the stationary distribution of the Land of Oz chain, the long-run fraction of nice days, the mean time between nice days, and the probability that a rainy day is followed two days later by another rainy day.
The stationary equations (3) are $\pi_R = \frac12\pi_R + \frac12\pi_N + \frac14\pi_S$, $\pi_N = \frac14\pi_R + \frac14\pi_S$ and $\pi_S = \frac14\pi_R + \frac12\pi_N + \frac12\pi_S$. The chain is unchanged when rain and snow exchange their labels, so exchanging $\pi_R$ and $\pi_S$ in a stationary distribution gives another one. The chain is irreducible, so by Theorem 3 there is only one, and therefore $\pi_R = \pi_S$. Then $\pi_N = \frac12\pi_R$ from the second equation, and $\pi_R + \frac12\pi_R + \pi_R = 1$ gives $\pi = (\frac25, \frac15, \frac25)$. By Theorem 7 the long-run fraction of nice days is $\frac15$, and by Theorem 4 the mean time between them is 5 days. The two-day probability is $(P^2)_{RR} = \frac12\cdot\frac12 + \frac14\cdot\frac12 + \frac14\cdot\frac14 = \frac{7}{16}$.
Problem 2 (which pattern comes first). A fair coin is tossed until two consecutive tosses read heads, heads (HH) or tails, heads (TH). Find the probability that HH comes first and the expected number of tosses.
The state is the part of the past that matters: the start (no toss yet), H (last toss heads, no pattern yet), T (last toss tails), and the two absorbing patterns. From the start, H or T with probability $\frac12$ each. From H, heads completes HH and tails leads to T. From T, heads completes TH and tails stays at T. With transient states in the order start, H, T and absorbing states HH, TH,
$$Q = \begin{pmatrix} 0 & 1/2 & 1/2 \\ 0 & 0 & 1/2 \\ 0 & 0 & 1/2 \end{pmatrix}, \qquad R = \begin{pmatrix} 0 & 0 \\ 1/2 & 0 \\ 0 & 1/2 \end{pmatrix}.$$
$I - Q$ is upper triangular, and solving $(I - Q)N = I$ column by column gives
$$N = \begin{pmatrix} 1 & 1/2 & 3/2 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{pmatrix}, \qquad N\mathbf{1} = \begin{pmatrix} 3 \\ 2 \\ 2 \end{pmatrix}, \qquad NR = \begin{pmatrix} 1/4 & 3/4 \\ 1/2 & 1/2 \\ 0 & 1 \end{pmatrix}.$$
By Theorem 8, HH comes first with probability 0.25 and the game lasts 3 tosses on average. The reason is visible in the chain: once a tail has appeared, HH can never come first, because the first head after that tail completes TH. HH wins only if the first two tosses are both heads.
Problem 3 (a two-state chain). A chain on two states has $p_{12} = a$ and $p_{21} = b$, with $0 < a + b < 2$. Find $P^n$, the stationary distribution and the rate of convergence. Evaluate for $a = 3/50$ and $b = 2/25$, close to the weekly switching probabilities that Hidden Markov Models estimates for the low and high seasons of deaths in Iowa.
The stationary equation $\pi_1 = \pi_1(1 - a) + \pi_2b$ gives $\pi_1a = \pi_2b$, so $\pi = \big(\frac{b}{a+b}, \frac{a}{a+b}\big)$; it is detailed balance, so the chain is reversible. Let $\lambda = 1 - a - b$. The claim is
$$P^n = \mathbf{1}\pi + \frac{\lambda^n}{a + b}\begin{pmatrix} a & -a \\ -b & b \end{pmatrix}.$$
For $n = 0$ the right side is the identity (check the diagonal: $\frac{b}{a+b} + \frac{a}{a+b} = 1$). For the induction step multiply by $P$ on the right: $\mathbf{1}\pi P = \mathbf{1}\pi$, and the second matrix times $P$ is $\lambda$ times itself, since its rows are multiples of $(1, -1)$ and $(1, -1)P = (1 - a - b, -(1 - a - b))$. So $P^n \to \mathbf{1}\pi$ at the rate $\lvert\lambda\rvert^n$, and $\lambda$ is the second eigenvalue. With $a = \frac{3}{50}$ and $b = \frac{2}{25}$: $\pi = (\frac47, \frac37)$, $\lambda = 0.86$, so the distance from stationarity halves every $\ln 2/(-\ln 0.86) = 4.6$ weeks. The chain stays in state 1 for a geometric number of weeks with mean $1/a = 16.7$ weeks and in state 2 for $1/b = 12.5$ weeks. After 10 weeks from state 1, $p_{11}^{(10)} = \frac47 + \frac37(0.86)^{10} = 0.666$, still well above $\frac47$.
Problem 4 (a periodic class). For the site's closed class of three pages, find $P^n$ for every $n$, show that it has no limit, and find the limit of the averages $\frac1n\sum_{t<n}P^t$.
In the order introduction, the two other notes, $P$ has rows $(0, \frac12, \frac12)$, $(1, 0, 0)$, $(1, 0, 0)$. Then $P^2$ has rows $(1, 0, 0)$, $(0, \frac12, \frac12)$, $(0, \frac12, \frac12)$, and $P^3 = P^2P = P$ (row by row: the first row of $P^2$ picks the first row of $P$, and $(0, \frac12, \frac12)P = (1, 0, 0)$). So $P^n = P$ for odd $n$ and $P^n = P^2$ for even $n \ge 2$, and $P^n$ has no limit. The class has period 2 (Lemma 3: the introduction page returns only at even times). The average of $P^t$ over $t < n$ approaches $\frac12(P + P^2)$, whose rows are all $(\frac12, \frac14, \frac14)$, the stationary distribution of Theorem 3, in line with the proof of Theorem 2 and with the ergodic theorem.
Summary
- A Markov chain is defined by its path probabilities (1); $n$-step probabilities are the entries of $P^n$ (Theorem 1).
- Every finite chain has a stationary distribution (Theorem 2). An irreducible one has exactly one, positive everywhere (Theorem 3), and $\pi_i = 1/m_i$, the reciprocal of the mean return time (Theorem 4).
- An irreducible chain is regular exactly when it is aperiodic (Theorem 5); then $\lVert\mu P^n - \pi\rVert_{\mathrm{TV}} \le \delta(P^r)^{\lfloor n/r\rfloor}$ from every start (Theorem 6). Periodic chains do not converge, but their averages do.
- Along one path, the fraction of time at each state converges to $\pi$ with probability 1, aperiodic or not (Theorem 7).
- In an absorbing chain $N = (I - Q)^{-1}$ counts expected visits; $N\mathbf{1}$ gives expected times to absorption and $NR$ the absorption probabilities (Theorem 8). Stationary mass sits only on closed classes (Corollary 1).
- Detailed balance gives stationarity and reversibility (Theorem 9); the random walk on a graph has $\pi_i \propto \deg(i)$ (Theorem 10); for reversible chains the second eigenvalue bounds the distance from stationarity (Theorem 11).
- On this site: a link-following surfer is caught by three pages after a median of 29,632 clicks; inside the large class it mixes slowly because of a 45-page algebra cluster ($\lambda_2 = 0.99909$); teleportation with probability 0.15 brings every start within 0.04 of PageRank in 20 clicks.
What we have learned
A finite Markov chain has a long run, and when every state can reach every other it has exactly one, in which each state's share is the reciprocal of its mean return time. Whether the chain approaches that long run at fixed times depends on periodicity, and how fast depends on bottlenecks: on this site, three pages that catch the surfer and a cluster of algebra pages that holds it. Teleportation removes both, which is the practical reason PageRank has it.
The chains here are observed: the surfer's page is the state. Hidden Markov Models keeps the Markov chain and hides it. Only a noisy signal of each state is seen, and the forward algorithm, Viterbi decoding and Baum–Welch fitting recover what can be recovered, on Iowa's weekly deaths, whose high and low seasons play the part of the hidden states. Chains in continuous time and on infinite state spaces continue in The Poisson Process and Random Walks and Martingales.
References
- Grinstead, C. M., and Snell, J. L. (1997). Introduction to Probability (2nd rev. ed.), chapter 11 (Example 11.1, the Land of Oz; Definition 11.5; Theorems 11.3 to 11.6 on absorbing chains; Theorem 11.12, the law of large numbers for ergodic chains; Theorem 11.15, mean recurrence times; Theorem 11.17, the central limit theorem for Markov chains). American Mathematical Society. (Read in the GNU Free Documentation License version of 2006.) record · 22 pages
- Levin, D. A., and Peres, Y. (2017). Markov Chains and Mixing Times (2nd ed., with contributions by E. L. Wilmer). American Mathematical Society. https://doi.org/10.1090/mbk/107. Proposition 1.7, Lemma 1.13, Lemma 1.16, Corollary 1.17, Propositions 1.20, 1.23 and 1.32, Lemma 1.30, Proposition 4.2, Theorem 4.9, Lemmas 12.1, 12.2 and 12.18, Theorem C.1. (Read in the authors' copy.) record · 3 pages
- Norris, J. R. (1997). Markov Chains. Cambridge University Press. Section 1.7 (Theorems 1.7.5 and 1.7.7, Example 1.7.8) and section 1.10 (Theorem 1.10.2). (Read in the sections the author made available.) record · 3 pages
- Roberts, G. O., and Rosenthal, J. S. (2004). General state space Markov chains and MCMC algorithms. Probability Surveys, 1, 20–71. https://doi.org/10.1214/154957804100000024 (cited through Markov Chain Monte Carlo) record · 2 pages