3.2 Limiting Behaviour and Stationary Distributions
Where a Markov chain settles in the long run: stationary distributions $\pi P=\pi$, positive and null recurrence with $\pi_i=1/\mu_i$, the convergence theorem $p_{ij}^{(n)}\to\pi_j$ for irreducible aperiodic chains and the ergodic theorem for time averages, doubly stochastic matrices, reversibility and detailed balance, and birth–death chains on a countable state space.
Run the weather chain of §3.1 for a few weeks and the forecast for a day far ahead no longer depends on today's weather: every row of $P^n$ becomes the same vector $(\frac{24}{61},\frac{22}{61},\frac{15}{61})$. This vector is stationary: a chain started from it keeps the same distribution for ever. It is also the long-run fraction of days of each kind, and its reciprocals are the mean times between sunny, cloudy and rainy days. The same mathematics ranks web pages (PageRank is the stationary distribution of a random surfer), predicts the equilibrium of physical systems (the Ehrenfest urn), sets the steady-state queue lengths of Chapter 9, and is the reason why Markov chain Monte Carlo can sample from a posterior distribution that can only be written down up to a constant.
This section answers three questions for a Markov chain with transition matrix $P$. Existence and uniqueness: when does $\pi P=\pi$ have a probability solution, and when only one? The answer is positive recurrence, and then $\pi_i=1/\mu_i$, where $\mu_i$ is the mean return time to $i$. Convergence: when does $p_{ij}^{(n)}\to\pi_j$? The answer is irreducibility and aperiodicity, and the proof is a beautiful coupling argument. Computation: how is $\pi$ found quickly? For doubly stochastic matrices it is uniform, for reversible chains detailed balance $\pi_ip_{ij}=\pi_jp_{ji}$ reduces the equations to a product formula, and for birth–death chains this decides positive recurrence, null recurrence and transience in one stroke. CSIR NET questions ask for a stationary distribution, a mean return time or a limit of $P^n$, or for a verdict on statements such as "every finite irreducible chain converges to equilibrium", which is false because of periodicity.
Stationary Distributions
Throughout, $(X_n)$ is a Markov chain with state space $S$ (finite or countable) and transition matrix $P$, as in §3.1; distributions on $S$ are row vectors, and $\lambda P^n$ is the distribution of $X_n$ when $X_0\sim\lambda$.
The balance equation says that the probability flowing into $j$ in one step equals the probability sitting at $j$. Since $\sum_jp_{ij}=1$, it can also be read as "flow out of $j$ equals flow into $j$": $\pi_j\sum_{k\ne j}p_{jk}=\sum_{i\ne j}\pi_ip_{ij}$.
- If $X_0\sim\pi$ with $\pi$ stationary, then $X_n\sim\pi$ for every $n$. Moreover the chain is strictly stationary: $(X_m,X_{m+1},\dots,X_{m+k})$ has the same law as $(X_0,\dots,X_k)$ for all $m,k$.
- If $j$ is transient, then $\pi_j=0$ for every stationary distribution $\pi$.
- The set of stationary distributions is convex: if $\pi,\pi'$ are stationary and $0\le t\le1$, so is $t\pi+(1-t)\pi'$. Hence a chain with two different stationary distributions has infinitely many.
Proof. (1) $\pi P^n=(\pi P)P^{n-1}=\pi P^{n-1}=\cdots=\pi$, so $X_n\sim\pi$. By Theorem 3.1(a), $$P(X_m=i_0,\dots,X_{m+k}=i_k)=\pi_{i_0}\,p_{i_0i_1}\cdots p_{i_{k-1}i_k},$$ because $P(X_m=i_0)=\pi_{i_0}$; the right side does not depend on $m$.
(2) For every $n$, $\pi_j=\sum_i\pi_ip_{ij}^{(n)}$. For transient $j$, $p_{ij}^{(n)}\to0$ for every $i$ (Theorem 3.6). The terms $\pi_ip_{ij}^{(n)}$ are dominated by $\pi_i$, and $\sum_i\pi_i=1$, so dominated convergence (for series) gives $\pi_j=\lim_n\sum_i\pi_ip_{ij}^{(n)}=0$.
(3) The equations $\lambda P=\lambda$, $\lambda\ge0$, $\sum\lambda_i=1$ are preserved by convex combinations. If $\pi\ne\pi'$, the distributions $t\pi+(1-t)\pi'$, $0\le t\le1$, are all different. ∎
Proof. Each $\nu_n$ is a probability vector, a point of the simplex $\Delta=\{x\in\mathbb{R}^S:x_i\ge0,\ \sum x_i=1\}$, which is closed and bounded in $\mathbb{R}^{|S|}$ and hence compact. By Bolzano–Weierstrass some subsequence $\nu_{n_r}$ converges to a point $\pi\in\Delta$. Now $$\nu_nP-\nu_n=\frac1n\sum_{k=0}^{n-1}\left(\lambda P^{k+1}-\lambda P^k\right)=\frac{\lambda P^n-\lambda}{n},$$ whose entries lie in $[-\frac1n,\frac1n]$. Letting $n=n_r\to\infty$ (matrix multiplication by the finite matrix $P$ is continuous) gives $\pi P-\pi=0$. ∎
Both uses of finiteness are essential. For the walk on $\mathbb{Z}$ the averages $\nu_n$ spread their mass ever more thinly, and every limit is the zero vector: mass "escapes to infinity". We shall see that the symmetric walk on $\mathbb{Z}$ has no stationary distribution at all. Note also that Theorem 3.16 says nothing about uniqueness, and that the Cesàro averages are needed: $P^n$ itself may fail to converge.
Positive and Null Recurrence; $\pi_i=1/\mu_i$
A recurrent state is visited infinitely often, but the gaps between visits may have finite or infinite mean. This distinction decides whether a stationary distribution exists.
The key construction counts visits during one excursion. For a fixed state $k$, let $\gamma_i^k$ be the expected number of visits to $i$ before the chain, started at $k$, first returns to $k$:
$$\gamma_i^k=E_k\sum_{n=0}^{T_k-1}\mathbf 1\{X_n=i\}.$$Proof. Only time $0$ is spent at $k$ before $T_k$, so $\gamma_k^k=1$. Summing over $i$ counts every time point $0,1,\dots,T_k-1$, so $\sum_i\gamma_i^k=E_k(T_k)=\mu_k$ (Tonelli).
Invariance. Since the chain is recurrent, $T_k\lt\infty$ almost surely and $X_{T_k}=k=X_0$, so the excursion may equally be counted over the times $1,\dots,T_k$: $$\gamma_j^k=E_k\sum_{n=1}^{T_k}\mathbf 1\{X_n=j\}=\sum_{n\ge1}P_k(X_n=j,\ n\le T_k).$$ The event $\{n\le T_k\}=\{T_k\le n-1\}^c$ is determined by $X_0,\dots,X_{n-1}$, so by the Markov property $$P_k(X_{n-1}=i,\ X_n=j,\ n\le T_k)=P_k(X_{n-1}=i,\ n\le T_k)\,p_{ij}.$$ Summing over $i$ and $n\ge1$, and putting $m=n-1$, $$\gamma_j^k=\sum_ip_{ij}\sum_{m\ge0}P_k(X_m=i,\ m\le T_k-1)=\sum_ip_{ij}\,E_k\sum_{m=0}^{T_k-1}\mathbf 1\{X_m=i\}=\sum_i\gamma_i^kp_{ij}.$$ Positivity and finiteness. By irreducibility choose $m,n$ with $p_{ki}^{(m)}\gt0$ and $p_{ik}^{(n)}\gt0$. Invariance gives $\gamma^k=\gamma^kP^m=\gamma^kP^n$, so $\gamma_i^k\ge\gamma_k^kp_{ki}^{(m)}=p_{ki}^{(m)}\gt0$ and $1=\gamma_k^k\ge\gamma_i^kp_{ik}^{(n)}$, whence $\gamma_i^k\le1/p_{ik}^{(n)}\lt\infty$. ∎
Proof. For $j\ne k$, expand $\lambda_j=\sum_{i_0}\lambda_{i_0}p_{i_0j}$, splitting off the term $i_0=k$ (where $\lambda_k=1$), and substitute the same expansion for $\lambda_{i_0}$ again and again: $$\lambda_j=p_{kj}+\sum_{i_0\ne k}p_{ki_0}p_{i_0j}+\cdots+\sum_{i_0,\dots,i_{n-1}\ne k}p_{ki_{n-1}}\cdots p_{i_0j}+\sum_{i_0,\dots,i_n\ne k}\lambda_{i_n}p_{i_ni_{n-1}}\cdots p_{i_0j}.$$ The last sum is nonnegative; the others add up to $\sum_{m=1}^{n+1}P_k(X_m=j,\ T_k\ge m)$. Letting $n\to\infty$ gives $\lambda_j\ge\sum_{m\ge1}P_k(X_m=j,\ T_k\gt m)=\gamma_j^k$ (for $j\ne k$, $X_m=j$ forces $T_k\ne m$). For $j=k$ both sides equal $1$.
If $P$ is recurrent, $\gamma^k$ is invariant (Theorem 3.17), so $\nu=\lambda-\gamma^k\ge0$ is an invariant measure with $\nu_k=0$. For any $i$ choose $n$ with $p_{ik}^{(n)}\gt0$; then $0=\nu_k=\sum_j\nu_jp_{jk}^{(n)}\ge\nu_ip_{ik}^{(n)}$, so $\nu_i=0$. ∎
For an irreducible chain the following are equivalent:
(i) every state is positive recurrent; (ii) some state is positive recurrent; (iii) the chain has a stationary distribution.
When they hold, the stationary distribution is unique and is given by $\pi_i=\dfrac1{\mu_i}\gt0$ for every $i$. In particular: positive recurrence is a class property; every irreducible chain on a finite state space is positive recurrent and has exactly one stationary distribution; and an irreducible null recurrent or transient chain has no stationary distribution.
Proof. (i)$\Rightarrow$(ii) is trivial. (ii)$\Rightarrow$(iii): if $k$ is positive recurrent it is recurrent, so the irreducible chain is recurrent (Theorem 3.8), and $\gamma^k$ is an invariant measure with total mass $\mu_k\lt\infty$ (Theorem 3.17). Then $\pi=\gamma^k/\mu_k$ is a stationary distribution.
(iii)$\Rightarrow$(i): let $\pi$ be stationary. Some $\pi_i\gt0$; for any $k$ choose $n$ with $p_{ik}^{(n)}\gt0$; then $\pi_k=\sum_j\pi_jp_{jk}^{(n)}\ge\pi_ip_{ik}^{(n)}\gt0$. So $\lambda=\pi/\pi_k$ is an invariant measure with $\lambda_k=1$, and Theorem 3.18 gives $\gamma^k\le\lambda$. Summing over $i$, $E_k(T_k)=\sum_i\gamma^k_i\le\sum_i\pi_i/\pi_k=1/\pi_k\lt\infty$. (Here $\gamma^k$ is defined even if $T_k$ might be infinite, and $\sum_i\gamma_i^k=E_k(T_k)$ still holds.) A finite mean forces $T_k\lt\infty$ almost surely, so $k$ is recurrent and in fact positive recurrent; $k$ was arbitrary.
Formula and uniqueness: since the chain is now known to be recurrent, Theorem 3.18 gives $\pi/\pi_k=\gamma^k$, and summing, $1/\pi_k=\sum_i\gamma^k_i=\mu_k$. Every stationary distribution therefore equals $(1/\mu_k)_k$, so there is only one. For finite irreducible chains, Theorem 3.16 provides a stationary distribution, so (iii) holds. ∎
Two consequences are worth stating. First, for an irreducible positive recurrent chain, $\gamma^k_i=\pi_i/\pi_k$: the expected number of visits to $i$ between two visits to $k$ is $\pi_i/\pi_k$ (Exercise II.8). Second, the symmetric random walk on $\mathbb{Z}$ is null recurrent. It is recurrent (§3.1), and the counting measure $\lambda_i\equiv1$ is invariant because every column of $P$ sums to $1$ ($\lambda_j=\frac12\lambda_{j-1}+\frac12\lambda_{j+1}$). By Theorem 3.18 every invariant measure is a multiple of it, and none has finite mass. So there is no stationary distribution and, by Theorem 3.19, $\mu_0=\infty$, in agreement with the generating-function computation $F_{00}'(1^-)=\infty$ of §3.1.
Convergence to Equilibrium and the Ergodic Theorem
A stationary distribution is an equilibrium. The next question is whether the chain actually reaches it from an arbitrary start, that is, whether $P(X_n=j)\to\pi_j$. The flip chain $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ shows that periodicity can prevent this: its stationary distribution is $(\frac12,\frac12)$, but $p_{11}^{(n)}$ alternates $0,1,0,1,\dots$. Periodicity turns out to be the only obstruction.
Proof (coupling). Let $(X_n)$ be Markov$(\lambda,P)$ and $(Y_n)$ an independent Markov$(\pi,P)$ chain, so $P(Y_n=j)=\pi_j$ for all $n$. The pair $W_n=(X_n,Y_n)$ is a Markov chain on $S\times S$ with transition probabilities $\tilde p_{(i,k)(j,l)}=p_{ij}p_{kl}$, and $\tilde\pi_{(i,k)}=\pi_i\pi_k$ is a stationary distribution for it.
$W$ is irreducible. By Theorem 3.12(b), irreducibility and aperiodicity give, for all $i,j,k,l$, an $N$ such that $p_{ij}^{(n)}\gt0$ and $p_{kl}^{(n)}\gt0$ for all $n\ge N$; hence $\tilde p_{(i,k)(j,l)}^{(n)}=p_{ij}^{(n)}p_{kl}^{(n)}\gt0$. (This is exactly where aperiodicity is used: for the flip chain, $W$ started at $(1,2)$ never reaches the diagonal.)
$W$ is recurrent. It is irreducible with a stationary distribution, so it is positive recurrent by Theorem 3.19. Fix $b\in S$ and let $T=\inf\{n\ge0:X_n=Y_n=b\}$. By Theorem 3.8(2), $f_{(i,k),(b,b)}=1$ from every starting pair, so $P(T\lt\infty)=1$.
Coupling. Define $Z_n=X_n$ for $n\lt T$ and $Z_n=Y_n$ for $n\ge T$. By the strong Markov property at $T$ (Theorem 3.4), after time $T$ both $X$ and $Y$ evolve as fresh chains from $b$, so $(Z_n)$ is again Markov$(\lambda,P)$ and $P(Z_n=j)=P(X_n=j)$. Hence $$\left|P(X_n=j)-\pi_j\right|=\left|P(Z_n=j)-P(Y_n=j)\right|=\left|P(Z_n=j,\,n\lt T)-P(Y_n=j,\,n\lt T)\right|,$$ because $Z_n=Y_n$ on $\{n\ge T\}$. Summing over $j$, $\sum_j|P(X_n=j)-\pi_j|\le2P(T\gt n)\to0$. ∎
The bound $\sum_j|P(X_n=j)-\pi_j|\le2P(T\gt n)$ is the coupling inequality. Half the left side is the total variation distance $d_{TV}(\lambda P^n,\pi)=\max_{A\subseteq S}|P(X_n\in A)-\pi(A)|$, the standard measure of how far a chain is from equilibrium. The next theorem completes the picture for chains that are periodic, null recurrent or transient, and replaces "the distribution converges" by "time averages converge", which needs no aperiodicity.
Let $P$ be irreducible.
- If $P$ is transient or null recurrent, then $p_{ij}^{(n)}\to0$ for all $i,j$.
- If $P$ is positive recurrent with period $d$, then for all $i,j$ there is $r\in\{0,\dots,d-1\}$ such that $p_{ij}^{(m)}=0$ unless $m\equiv r\pmod d$, and $p_{ij}^{(nd+r)}\to d\,\pi_j$ as $n\to\infty$.
- (Ergodic theorem) For every initial distribution and every $j$, with probability one $$\frac1n\sum_{k=0}^{n-1}\mathbf 1\{X_k=j\}\ \longrightarrow\ \frac1{\mu_j}\qquad(=\pi_j\text{ if positive recurrent},\ 0\text{ otherwise}).$$ Consequently $\frac1n\sum_{k=1}^{n}p_{ij}^{(k)}\to\frac1{\mu_j}$, and in the positive recurrent case $\frac1n\sum_{k=0}^{n-1}f(X_k)\to\sum_j\pi_jf(j)$ almost surely for every bounded $f$.
Proof. (3) If the chain is transient, the number of visits to $j$ is finite almost surely (Theorem 3.6), and dividing by $n$ gives $0=1/\mu_j$. If it is recurrent, it hits $j$ at a finite time almost surely (Theorem 3.8(2)); after that, by the strong Markov property, the lengths $L_1,L_2,\dots$ of the successive excursions from $j$ back to $j$ are iid with mean $\mu_j$. Let $V_n$ be the number of visits to $j$ before time $n$. The $V_n$-th visit happens before time $n$, and the $(V_n+1)$-th at or after it, so $$\frac{T+L_1+\cdots+L_{V_n-1}}{V_n}\ \le\ \frac{n}{V_n}\ \le\ \frac{T+L_1+\cdots+L_{V_n}}{V_n},$$ where $T$ is the first hitting time of $j$. Since $V_n\to\infty$, the strong law of large numbers (§2.3; it also holds for nonnegative variables with infinite mean, with limit $\infty$) makes both bounds tend to $\mu_j$. So $V_n/n\to1/\mu_j$. Taking expectations (bounded convergence, $0\le V_n/n\le1$) gives the Cesàro statement, and the statement for $f$ follows by summing over $j$, first for $f$ with finite support and then by approximation.
(2) Let $C_0,\dots,C_{d-1}$ be the cyclic classes (Theorem 3.12(c)). Restricted to a class $C_r$, the matrix $P^d$ is irreducible and aperiodic, and $(d\pi_j)_{j\in C_r}$ is stationary for it (by (3), the chain spends a fraction $1/d$ of its time in each class, so $\pi(C_r)=\frac1d$). Theorem 3.20 applied to $P^d$ on $C_r$ gives the claim.
(1) For transient chains this is Theorem 3.6. For null recurrent chains we prove the weaker Cesàro statement $\frac1n\sum_{k\le n}p_{ij}^{(k)}\to0$ in (3); the full statement $p_{ij}^{(n)}\to0$ follows by a coupling argument like that of Theorem 3.20 (Orey's theorem), which we omit. ∎
Proof sketch. Run two copies of the chain in blocks of $m$ steps. From any pair of current states $(i,k)$, the laws of the positions $m$ steps later overlap in mass $\sum_j\min\left(p_{ij}^{(m)},p_{kj}^{(m)}\right)\ge s\delta$, so the two copies can be coupled to land on the same state with probability at least $s\delta$ (a "maximal coupling"), after which they move together. Hence $P(T\gt km)\le(1-s\delta)^k$, and the coupling inequality gives the bound. For the spectral statement, write $P^n=\sum_k\lambda_k^nE_k$ with the spectral projections $E_k$; the term $k=1$ is $\mathbf 1\pi$, and the others are $O(\beta^n)$. ∎
For the two-state chain of §3.1, $\beta=|1-a-b|$; for the weather chain $\beta=\frac{2+\sqrt3}{10}$. The quantity $1-\beta$ is the spectral gap: a small gap means slow mixing, as in Interactive 1's "two rooms" chain, where a rare connection between two clusters makes $\beta=0.96$.
Doubly Stochastic Matrices and Reversible Chains
Solving $\pi P=\pi$ directly means solving $|S|$ linear equations. Two structural properties of $P$ make the solution immediate. Recognising them quickly is a large part of answering exam questions.
Proof. (a) $(uP)_j=\frac1s\sum_ip_{ij}$, which equals $\frac1s$ for every $j$ iff every column sums to $1$. (b) Uniqueness and $\mu_i=1/\pi_i=s$ come from Theorem 3.19. (c) The counting measure $\lambda_i\equiv1$ is invariant (its balance equation is the column-sum condition). If the chain were positive recurrent it would be recurrent, so by Theorem 3.18 every invariant measure would be a multiple of the summable measure $\pi$; but $\lambda$ is not summable. ∎
(b) Let $P$ be irreducible with stationary distribution $\pi$, let $(X_n)$ be Markov$(\pi,P)$ and fix $N$. Then $Y_n=X_{N-n}$, $0\le n\le N$, is Markov$(\pi,\hat P)$ with $\hat p_{ij}=\dfrac{\pi_j\,p_{ji}}{\pi_i}$. Hence the chain run backwards in equilibrium has the same law as forwards, $\hat P=P$, if and only if it is reversible.
Proof. (a) $\sum_i\lambda_ip_{ij}=\sum_i\lambda_jp_{ji}=\lambda_j\sum_ip_{ji}=\lambda_j$.
(b) All $\pi_i\gt0$ (Theorem 3.19), so $\hat P$ is defined; it is stochastic because $\sum_j\hat p_{ij}=\frac1{\pi_i}\sum_j\pi_jp_{ji}=\frac{\pi_i}{\pi_i}=1$, by stationarity. By Theorem 3.1(a), $$P(Y_0=i_0,\dots,Y_N=i_N)=P(X_0=i_N,\dots,X_N=i_0)=\pi_{i_N}p_{i_Ni_{N-1}}\cdots p_{i_1i_0}.$$ Rewriting each factor as $p_{i_{k}i_{k-1}}=\hat p_{i_{k-1}i_k}\,\pi_{i_{k-1}}/\pi_{i_k}$, the $\pi$'s telescope and the product becomes $\pi_{i_0}\hat p_{i_0i_1}\cdots\hat p_{i_{N-1}i_N}$; so $(Y_n)$ is Markov$(\pi,\hat P)$. Finally $\hat P=P$ means $\pi_jp_{ji}=\pi_ip_{ij}$ for all $i,j$. ∎
Detailed balance is sufficient for stationarity but not necessary. It replaces $|S|$ coupled equations by the one-line recursion $\pi_j=\pi_ip_{ij}/p_{ji}$ along any path, which is why one always tries it first. When does it succeed? Kolmogorov's criterion answers without knowing $\pi$.
Proof. Necessity: multiply the detailed balance equations $\pi_{i_k}p_{i_ki_{k+1}}=\pi_{i_{k+1}}p_{i_{k+1}i_k}$ for $k=0,\dots,n-1$ and cancel $\prod_k\pi_{i_k}\gt0$. Sufficiency (sketch): the criterion implies that $p_{ij}\gt0\iff p_{ji}\gt0$ (apply it to the cycle $i,j$ followed by a path back from $j$ to $i$). Fix a state $0$ and, for each $j$, a path $0=j_0,j_1,\dots,j_m=j$ with positive transition probabilities; put $\lambda_j=\prod_{k}\frac{p_{j_kj_{k+1}}}{p_{j_{k+1}j_k}}$. The criterion shows that $\lambda_j$ does not depend on the path chosen, and then $\lambda_jp_{jl}=\lambda_lp_{lj}$ (extend the path to $j$ by one step to $l$). By Theorem 3.24(a), $\lambda$ is invariant, so by uniqueness it is a multiple of $\pi$. ∎
Proof. Connectedness gives irreducibility. $\pi_ip_{ij}=\frac{w_i}{W}\cdot\frac{w_{ij}}{w_i}=\frac{w_{ij}}W$ is symmetric in $i,j$, so detailed balance holds, and $\sum_i\pi_i=1$. Apply Theorems 3.24(a) and 3.19. For unit weights $w_i=\deg i$ and $W=\sum_i\deg i=2|E|$ (each edge counted from both ends). ∎
Conversely, every reversible chain is a random walk on a weighted graph, with weights $w_{ij}=\pi_ip_{ij}$. Reversible chains are exactly the chains for which the electrical-network analogy and the spectral theory of symmetric matrices apply: $D^{1/2}PD^{-1/2}$ with $D=\operatorname{diag}(\pi)$ is symmetric, so $P$ has real eigenvalues.
Birth–Death Chains on a Countable State Space
On an infinite state space a chain can be positive recurrent, null recurrent or transient. For chains that move only to neighbouring states, all three cases are decided by two explicit series.
Let $p_{i,i+1}=p_i\gt0$ ($i\ge0$), $p_{i,i-1}=q_i\gt0$ ($i\ge1$), $p_{ii}=r_i=1-p_i-q_i\ge0$ (with $q_0=0$), and define
$$\theta_0=1,\quad\theta_n=\frac{p_0p_1\cdots p_{n-1}}{q_1q_2\cdots q_n};\qquad\rho_0=1,\quad\rho_n=\frac{q_1q_2\cdots q_n}{p_1p_2\cdots p_n}.$$- Every invariant measure satisfies detailed balance and is a multiple of $(\theta_n)$. The chain is positive recurrent iff $\sum_n\theta_n\lt\infty$, and then $\pi_n=\theta_n\big/\sum_k\theta_k$; the chain is reversible.
- The chain is recurrent iff $\sum_n\rho_n=\infty$. More precisely, $P_i(\text{ever hit }0)=\dfrac{\sum_{m\ge i}\rho_m}{\sum_{m\ge0}\rho_m}$ for $i\ge1$ (equal to $1$ if the denominator diverges).
Hence: positive recurrent if $\sum\theta_n\lt\infty$; null recurrent if $\sum\theta_n=\infty=\sum\rho_n$; transient if $\sum\rho_n\lt\infty$.
Proof. (1) Let $\lambda$ be invariant. Add the balance equations $\lambda_j=\sum_i\lambda_ip_{ij}$ for $j=0,1,\dots,n$. On the left we get $\sum_{j\le n}\lambda_j$. On the right, every transition between two states of $\{0,\dots,n\}$ is counted, and the only transition into $\{0,\dots,n\}$ from outside is $n+1\to n$. So $$\sum_{j\le n}\lambda_j=\sum_{j\le n}\lambda_j(1-[j=n]\,p_n)+\lambda_{n+1}q_{n+1},$$ i.e. $\lambda_np_n=\lambda_{n+1}q_{n+1}$ for every $n$: detailed balance across each cut. By induction $\lambda_n=\lambda_0\theta_n$. A stationary distribution exists iff $\sum\theta_n\lt\infty$ (and $\lambda_0\gt0$), and the claim follows from Theorem 3.19.
(2) Fix $N\gt i$ and let $u_i=P_i(\text{hit }N\text{ before }0)$, $0\le i\le N$. First-step analysis gives $u_0=0$, $u_N=1$ and $u_i=p_iu_{i+1}+q_iu_{i-1}+r_iu_i$, i.e. $p_i(u_{i+1}-u_i)=q_i(u_i-u_{i-1})$. Hence $u_{m+1}-u_m=\rho_m(u_1-u_0)$, and summing, $$u_i=\frac{\sum_{m=0}^{i-1}\rho_m}{\sum_{m=0}^{N-1}\rho_m}.$$ (This is the gambler's ruin formula of §1.2 with state-dependent odds.) The events $\{\text{hit }N\text{ before }0\}$ decrease, as $N\to\infty$, to $\{\text{never hit }0\}$, because the chain cannot reach $N$ before time $N-i$. So $P_i(\text{never hit }0)=\lim_Nu_i=\sum_{m\lt i}\rho_m\big/\sum_{m\ge0}\rho_m$, which is $0$ iff $\sum\rho_m=\infty$. Finally $f_{00}=r_0+p_0P_1(\text{hit }0)$, which equals $1$ iff $P_1(\text{hit }0)=1$. ∎
- A stationary distribution does not imply convergence. The flip chain $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ and the Ehrenfest urn have unique stationary distributions, but $P^n$ oscillates. Aperiodicity is needed for $p_{ij}^{(n)}\to\pi_j$; Cesàro averages converge regardless.
- Uniqueness needs irreducibility (one closed class). $P=I_2$ has every distribution stationary; Example 4 has a one-parameter family. Two different stationary distributions always give infinitely many (convexity).
- Infinite irreducible chains may have none. The symmetric walk on $\mathbb{Z}$ (null recurrent) and the walk with drift (transient) have no stationary distribution. "Finite" is essential in Theorem 3.16.
- An invariant measure is not a stationary distribution. The counting measure is invariant for the symmetric walk on $\mathbb{Z}$ but has infinite mass. For transient chains invariant measures need not be unique: for the walk on $\mathbb{Z}$ with $p\ne\frac12$, both $1$ and $(p/q)^i$ are invariant.
- $p_{ii}^{(n)}\to0$ does not mean transience. Null recurrent states have $p_{ii}^{(n)}\to0$ too. And $\pi_i=1/\mu_i$ holds for irreducible chains; in a reducible chain a stationary distribution can vanish on a positive recurrent state of another closed class.
- Doubly stochastic iff uniform $\pi$ (finite chains). Row sums are always $1$; it is the column sums that make $\pi$ uniform. An infinite irreducible doubly stochastic chain (the shift $i\mapsto i+1$, or the walk on $\mathbb{Z}$) has no stationary distribution.
- Detailed balance is sufficient, not necessary. The biased walk on a $3$-cycle has a uniform stationary distribution but is not reversible (Example 6). Solving $\pi_ip_{ij}=\pi_jp_{ji}$ for a non-reversible chain gives inconsistent equations, not a wrong answer: if detailed balance fails, use the global balance equations.
- Rows converge, columns do not have to. $P^n\to\mathbf 1\pi$ means every row tends to $\pi$; the columns tend to constant vectors $\pi_j\mathbf 1$.
- Limits of reducible chains depend on the start. $\lim_np_{ij}^{(n)}=f_{ij}\pi_j$ (aperiodic closed class), so different rows of $\lim P^n$ differ.
- Irreducible and aperiodic is not enough on infinite spaces. The lazy walk on $\mathbb{Z}$ with drift is irreducible and aperiodic, but $p_{ij}^{(n)}\to0$; positive recurrence is also required.
- Bipartite graphs give periodic walks. The knight's walk and the walk on a cube have stationary distributions $\propto$ degree but period $2$.
Exercises
- 1 For $P=\begin{pmatrix}0.2&0.8\\0.6&0.4\end{pmatrix}$, find $\pi$, the mean return times and $\lim_nP^n$.
- 2 For the chain on $\{1,2,3\}$ with $p_{ij}=\frac12$ ($i\ne j$), find $\pi$ and show that $p_{11}^{(n)}=\frac13+\frac23\left(-\frac12\right)^n$.
- 3 Find the stationary distribution of $P=\begin{pmatrix}\frac12&\frac12&0\\0&\frac12&\frac12\\\frac12&0&\frac12\end{pmatrix}$ without solving any equations.
- 4 Find all stationary distributions of the chain on $\{1,2,3,4\}$ with rows $(\frac12,\frac12,0,0)$, $(\frac12,\frac12,0,0)$, $(\frac14,\frac14,\frac14,\frac14)$, $(0,0,0,1)$.
- 5 Let $P$ be irreducible with stationary distribution $\pi$. Show that $\pi$ is also stationary for the lazy chain $Q=\frac12(I+P)$, and that $Q$ is irreducible and aperiodic.
- 6 On the cycle $\mathbb{Z}_m=\{0,1,\dots,m-1\}$ ($m\ge3$) the chain moves $i\to i+1$ with probability $p$ and $i\to i-1$ with probability $1-p$ (mod $m$), $0\lt p\lt1$. Find $\pi$ and the period.
- 7 For which two-state chains $\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}$ is $\pi=(\frac13,\frac23)$? Which of them converge to $\pi$?
- 8 For the chain of §3.1, Exercise II.2 ($0\to1\to2\to3$, then $3\to0$ or $3\to1$ with probability $\frac12$ each), find $\pi$ and $\mu_0$, and check $\mu_0$ by computing $E_0(T_0)$ directly.
Type a $3\times3$ transition matrix (decimals or fractions such as 1/3). The lab solves $\pi P=\pi$, $\sum\pi_i=1$ (when the solution is unique), lists the mean return times $\mu_i=1/\pi_i$, and tests whether $P$ is doubly stochastic and whether detailed balance holds. It starts with the matrix of Exercise III.5; try the matrices of Exam corner E1 and Exercise III.4 too.
- 1 For the weather chain, find $\lim_nP(X_n=R\mid X_0=S)$, and the smallest $n$ for which every entry of $P^n$ is within $0.001$ of its limit.
- 2 For the Ehrenfest chain with $N=4$, find $\lim_np_{00}^{(2n)}$, $\lim_np_{01}^{(2n+1)}$ and $\lim_n\frac1n\sum_{k=1}^np_{00}^{(k)}$.
- 3 (Maintenance) The machine of §3.1, Example 2 earns ₹100 on each working day and costs ₹400 on each day under repair. Find the long-run average profit per day.
- 4 For the chain of Exercise I.8, find the smallest $m$ with all entries of $P^m$ positive. (Compare with Wielandt's bound $(s-1)^2+1$ for an $s$-state chain.)
- 5 For the two-state chain, show that $d_{TV}(\text{row }1\text{ of }P^n,\pi)=\frac{a}{a+b}|1-a-b|^n$.
- 6 Let $P$ be finite and irreducible. Prove that all rows of $P^n$ converge to a common limit if and only if $P$ is aperiodic.
- 7 In an irreducible positive recurrent chain, show that the expected number of visits to $j$ between two successive visits to $i$ is $\pi_j/\pi_i$. For the weather chain, find the expected number of rainy days between two consecutive sunny days.
- 8 The walk on the path $1-2-3-4$ moves to a uniformly chosen neighbour. Find $\pi$, the period, and $\lim_np_{11}^{(2n)}$.
- 1 Give a $3\times3$ doubly stochastic matrix that is not symmetric, and decide whether its chain is reversible.
- 2 For the simple random walk on the vertices of a cube, find $\pi$ and the mean return time to a vertex. Does $p_{vv}^{(n)}$ converge?
- 3 A knight moves at random on an empty $8\times8$ board. Find the mean return time to a corner and explain why $P(X_n=\text{corner})$ has no limit.
- 4 Verify detailed balance for $P=\begin{pmatrix}\frac12&\frac12&0\\\frac14&\frac12&\frac14\\0&\frac12&\frac12\end{pmatrix}$ with $\pi=(\frac14,\frac12,\frac14)$.
- 5 For $P=\begin{pmatrix}0&\frac12&\frac12\\\frac13&0&\frac23\\\frac14&\frac34&0\end{pmatrix}$, use Kolmogorov's criterion to show that the chain is not reversible, then find $\pi$ from the global balance equations.
- 6 (Metropolis algorithm) Let $\pi$ be a positive distribution on a finite set and $Q$ a symmetric irreducible transition matrix. Define $p_{ij}=q_{ij}\min(1,\pi_j/\pi_i)$ for $j\ne i$ and $p_{ii}=1-\sum_{j\ne i}p_{ij}$. Prove that $P$ is reversible with respect to $\pi$.
- 7 Find the time-reversed chain $\hat P$ of the biased $3$-cycle of Example 6(a).
- 8 A random walk on a triangle uses edge weights $w_{12}=1$, $w_{13}=2$, $w_{23}=3$. Write down $P$ and find $\pi$.
- 1 For the reflecting walk of Example 7 with $p=0.25$, find $\pi$, $\mu_0$ and the long-run mean of $X_n$.
- 2 For the success-runs chain with constant $p_i=p\in(0,1)$, find $\pi$, $\mu_0$ and $\lim_nP(X_n=0)$.
- 3 Classify the birth–death chain with $p_{01}=1$ and $p_{k,k+1}=\frac{k+1}{2k+1}$, $p_{k,k-1}=\frac{k}{2k+1}$ for $k\ge1$.
- 4 For the walk on $\mathbb{Z}$ with $p\ne\frac12$, show that $\lambda_i=1$ and $\lambda_i=(p/q)^i$ are both invariant measures. Why does this not contradict Theorem 3.18?
- 5 A chain on $\{0,1,2,\dots\}$ has $p_{i,i+1}=p$, $p_{i,i-1}=q$, $p_{ii}=1-p-q$ for $i\ge1$, and $p_{01}=p$, $p_{00}=1-p$, where $p,q\gt0$ and $p+q\le1$. Find the condition for positive recurrence and the stationary distribution.
- 6 A birth–death chain has $p_{00}=p_{01}=\frac12$ and, for $k\ge1$, $p_{k,k+1}=\frac1{k+2}$, $p_{k,k-1}=\frac{k+1}{k+2}$. Show that it is positive recurrent and find $\pi_0$.
- 7 For the chain with $p_{01}=1$, $p_{i,i+1}=p$, $p_{i,i-1}=q=1-p$ ($i\ge1$) and $p\lt\frac12$, find $\pi_0$, the period, and $\lim_np_{00}^{(2n)}$.
- 8 Prove: if an irreducible recurrent chain has an invariant measure $\lambda$ with $\sum_i\lambda_i=\infty$, then it is null recurrent.
E1. CSIR Part B A Markov chain on $\{1,2,3\}$ has transition matrix $P=\begin{pmatrix}0&1&0\\\frac13&\frac13&\frac13\\0&\frac12&\frac12\end{pmatrix}$. The mean return time to state $1$ is (A) $3$; (B) $4$; (C) $6$; (D) $2$.
E2. CSIR Part B Let $P$ be a $4\times4$ doubly stochastic matrix all of whose entries are strictly positive. Then $\lim_{n\to\infty}P(X_n=1\mid X_0=3)$ (A) is $0$; (B) is $\frac14$; (C) is $\frac12$; (D) does not exist in general.
E3. CSIR Part B GATE ST A particle performs a simple random walk on the wheel graph formed by a $5$-cycle together with a hub joined to all five cycle vertices. Starting from the hub, the expected number of steps until it first returns to the hub is (A) $4$; (B) $5$; (C) $6$; (D) $\frac{20}3$.
E4. CSIR Part C Which of the following statements are true? (One or more options may be correct.) (A) Every Markov chain on a finite state space has at least one stationary distribution. (B) If a finite chain is irreducible, then $P^n$ converges to a matrix with identical rows. (C) If a finite chain has two different stationary distributions, then it has infinitely many. (D) Every irreducible chain on a countably infinite state space has a stationary distribution.
E5. CSIR Part C On $\{0,1,2,\dots\}$ let $p_{01}=1$ and, for $i\ge1$, $p_{i,i+1}=p$, $p_{i,i-1}=1-p$, where $0\lt p\lt1$. Which of the following are true? (A) For $p=\frac13$ the chain has a stationary distribution with $\pi_0=\frac14$. (B) For $p=\frac12$ the chain is null recurrent. (C) For $p=\frac12$ the mean return time to $0$ is finite. (D) For $p=\frac23$ the chain is positive recurrent.
E6. CSIR Part C Let $P=\begin{pmatrix}0&\frac23&\frac13\\\frac13&0&\frac23\\\frac23&\frac13&0\end{pmatrix}$. Which of the following are true? (A) The uniform distribution is the unique stationary distribution of $P$. (B) The chain is reversible. (C) $p_{12}^{(n)}\to\frac13$ as $n\to\infty$. (D) The time-reversed chain in equilibrium has transition matrix $P^{\mathsf T}$.
Suggested plan — 3 lectures × 60 min.
- Stationary distributions. Open with Interactive 1 on the weather chain: the rows of $P^n$ merging. Definition 3.7, Theorem 3.15, Theorem 3.16 (the Cesàro proof is short and elegant), Example 1 on the board. Definition 3.8 and the statement of Theorem 3.19; prove Theorem 3.17 and the formula $\pi_i=1/\mu_i$. Example 2 (success runs) as the showcase of positive, null and transient behaviour.
- Convergence. The flip chain as a warning; Theorem 3.20 with the coupling proof (draw the two chains meeting). Theorem 3.21 (state all three parts; prove the ergodic theorem from the SLLN). Interactive 1 again: Ehrenfest (no convergence) and two rooms (slow convergence, spectral gap). Examples 3 and 4.
- Structure and countable chains. Theorem 3.23, detailed balance (Definition 3.9, Theorem 3.24), Kolmogorov's criterion, random walks on graphs with Example 5 (let the class compute the king's degrees). Example 6. Theorem 3.27 and Example 7 with Interactive 2 at $p=0.35$, $0.5$, $0.55$. Finish with E4 and E5 done live.
Discussion questions. (1) Why does a periodic chain have a stationary distribution even though it never "settles down"? What does $\pi$ mean for it? (2) A reversible chain looks the same played forwards and backwards in equilibrium; can you tell from a film whether the weather chain is reversible? (3) Why can PageRank be computed by repeatedly multiplying a vector by a matrix with billions of rows, and why does the damping factor guarantee fast convergence?
Misconceptions to watch for. Solving $P\pi^{\mathsf T}=\pi^{\mathsf T}$ (right eigenvector) instead of $\pi P=\pi$; forgetting the normalisation $\sum\pi_i=1$; claiming that every irreducible chain converges (periodicity) or that every irreducible chain has a stationary distribution (infinite state spaces); confusing $\pi_i$ with $\mu_i$; using detailed balance for a non-reversible chain; believing that $p_{ii}^{(n)}\to0$ signals transience.
Suggested homework. I(1, 2, 4, 8), II(2, 3, 6, 7), III(2, 5, 6, 8), IV(1, 3, 6, 8); Exam corner E1, E5, E6.
Research question. A search engine ranks pages by the long-run fraction of time a random surfer spends on them. How is this "PageRank" a stationary distribution, why is a damping factor needed, and how quickly does the power method $\pi^{(k+1)}=\pi^{(k)}G$ find it?
Why it matters. PageRank made web search usable in the late 1990s, and the same idea now ranks scientific papers by citations, proteins in interaction networks, players in sports leagues and nodes in power grids. Each application is a Markov chain on a huge graph whose stationary distribution must be computed from a few hundred matrix–vector products, so the questions of existence, uniqueness and speed of convergence studied in this section are exactly the practical ones.
What to do.
- Take the five-page web A→B, A→C, B→C, C→A, D→A, D→B, D→C, D→E, E→D. Write the surfer's matrix $H$ (follow a uniformly chosen out-link). Classify its states and find all its stationary distributions. Explain why "rank = stationary probability" is not well defined for $H$ alone.
- Form the Google matrix $G=dH+\frac{1-d}{5}J$ with $d=0.85$ ($J$ = all ones). Show that $G$ is irreducible and aperiodic, so it has a unique stationary distribution to which $\pi^{(k)}$ converges from any start (Theorems 3.19 and 3.20).
- Run the power method from the uniform vector and record $\|\pi^{(k)}-\pi\|_1$ for $k=5,10,20,40$. Compare the decay with $d^k$ and with $\beta^k$, where $\beta$ is the second-largest eigenvalue modulus of $G$.
- Rank the pages and compare with ranking by number of in-links. Which page gains the most from being linked to by an important page?
Tools: Python with numpy (or any matrix calculator); a spreadsheet for the convergence table.
Hand in: The ranking with PageRank values to three decimals, the convergence table, and one paragraph explaining what the damping factor guarantees and what it changes.
Going further. Prove that every eigenvalue of $G$ other than $1$ has modulus at most $d$, so that $d$ controls the convergence however large the web is. Read about personalised PageRank (teleporting to a chosen set of pages) and how it is used for recommendations.
🧪 Self-check quiz
Q1. For an irreducible Markov chain on a finite state space with stationary distribution $\pi$, the mean return time to state $i$ is
Q2. An irreducible chain on $5$ states has a doubly stochastic transition matrix. Its stationary distribution gives state $3$ the probability
Q3. For $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$, which statement is true?
Q4. A simple random walk moves on a star graph: one centre joined to $4$ leaves (no other edges). In the long run the fraction of time spent at the centre is
Q5. The reflecting walk on $\{0,1,2,\dots\}$ that moves up with probability $\frac12$ and down (or stays at $0$) with probability $\frac12$ is