Chapter 3 · Markov Chains and Stochastic Processes

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$.

📘 Definition 3.7 — Invariant measures and stationary distributions
A measure on $S$ is a row vector $\lambda=(\lambda_i)_{i\in S}$ with $0\le\lambda_i\lt\infty$. It is invariant for $P$ if $\lambda P=\lambda$, that is, $$\lambda_j=\sum_{i\in S}\lambda_ip_{ij}\qquad\text{for every }j\in S\quad(\text{the global balance equations}).$$ An invariant measure $\pi$ with $\sum_i\pi_i=1$ is a stationary (invariant, equilibrium) distribution. Equivalently, $\pi$ is a left eigenvector of $P$ for the eigenvalue $1$ with nonnegative entries summing to $1$.

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}$.

📐 Theorem 3.15 — Basic properties of stationary distributions
  1. 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$.
  2. If $j$ is transient, then $\pi_j=0$ for every stationary distribution $\pi$.
  3. 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. ∎

📐 Theorem 3.16 — Existence on a finite state space
Every Markov chain on a finite state space has at least one stationary distribution. In fact, for every initial distribution $\lambda$, every limit point of the Cesàro averages $\nu_n=\frac1n\sum_{k=0}^{n-1}\lambda P^k$ is a stationary distribution.

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.

✏️ Example 1 — The weather chain in equilibrium
For the weather chain of §3.1 (states S, C, R), $$P=\begin{pmatrix}0.6&0.3&0.1\\0.3&0.4&0.3\\0.2&0.4&0.4\end{pmatrix},$$ find the stationary distribution, the long-run fraction of rainy days, and the mean number of days from one rainy day to the next. How fast does $P^n$ approach its limit?
Equations $\pi P=\pi$ reads $\pi_S=0.6\pi_S+0.3\pi_C+0.2\pi_R$, $\pi_C=0.3\pi_S+0.4\pi_C+0.4\pi_R$, $\pi_R=0.1\pi_S+0.3\pi_C+0.4\pi_R$. One equation is redundant (the three add up to an identity), so replace it by $\pi_S+\pi_C+\pi_R=1$.
Solve The third equation gives $0.6\pi_R=0.1\pi_S+0.3\pi_C$; the first gives $0.4\pi_S=0.3\pi_C+0.2\pi_R$. Put $\pi_R=1$: then $0.1\pi_S+0.3\pi_C=0.6$ and $0.4\pi_S-0.3\pi_C=0.2$; adding, $0.5\pi_S=0.8$, so $\pi_S=1.6$ and $\pi_C=\frac{0.6-0.16}{0.3}=\frac{22}{15}$. Normalising $(1.6,\frac{22}{15},1)=\frac1{15}(24,22,15)$ gives $\pi=\left(\frac{24}{61},\frac{22}{61},\frac{15}{61}\right)\approx(0.393,0.361,0.246)$.
Interpretation The chain is finite, irreducible and aperiodic, so by Theorems 3.19–3.21 below, about $24.6\%$ of days are rainy in the long run, and the mean time from a rainy day to the next is $\mu_R=1/\pi_R=\frac{61}{15}\approx4.07$ days (similarly $\mu_S=\frac{61}{24}\approx2.54$, $\mu_C=\frac{61}{22}\approx2.77$).
Rate The eigenvalues of $P$ are $1$ and $\frac{2\pm\sqrt3}{10}\approx0.373,\ 0.027$ (trace $1.4$, determinant $0.01$). So $|p_{ij}^{(n)}-\pi_j|$ decays like $0.373^n$. Numerically, the largest error is $0.0015$ at $n=6$ and $0.00055$ at $n=7$: after a week the forecast has forgotten today's weather to three decimal places.

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.

📘 Definition 3.8 — Mean return time; positive and null recurrence
The mean return time (mean recurrence time) of state $i$ is $\mu_i=E_i(T_i)=\sum_{n\ge1}n\,f_{ii}^{(n)}+\infty\cdot(1-f_{ii})$, where $T_i=\inf\{n\ge1:X_n=i\}$. A recurrent state is positive recurrent if $\mu_i\lt\infty$ and null recurrent if $\mu_i=\infty$. (Transient states have $\mu_i=\infty$ automatically.)

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\}.$$
📐 Theorem 3.17 — An invariant measure from excursions
Let $P$ be irreducible and recurrent, and fix $k\in S$. Then $\gamma^k_k=1$, $\gamma^kP=\gamma^k$, $0\lt\gamma^k_i\lt\infty$ for every $i$, and $\sum_{i\in S}\gamma^k_i=\mu_k$.

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$. ∎

📐 Theorem 3.18 — Uniqueness of invariant measures
Let $P$ be irreducible and let $\lambda$ be an invariant measure with $\lambda_k=1$. Then $\lambda\ge\gamma^k$ entrywise. If in addition $P$ is recurrent, then $\lambda=\gamma^k$. Thus an irreducible recurrent chain has, up to a constant multiple, exactly one invariant measure.

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$. ∎

📐 Theorem 3.19 — Existence and uniqueness of the stationary distribution

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.

✏️ Example 2 — The success-runs chain: positive, null or transient
On $S=\{0,1,2,\dots\}$, from state $i$ the chain moves to $i+1$ with probability $p_i$ and to $0$ with probability $1-p_i$, where $0\lt p_i\lt1$. (Think of the length of the current run of successes in independent trials whose success probability depends on the run length.) Show that the chain is irreducible, that $P_0(T_0\gt n)=p_0p_1\cdots p_{n-1}$, and classify it for (a) $p_i=\left(\frac{i+1}{i+2}\right)^2$; (b) $p_i=\frac{i+1}{i+2}$; (c) $p_i=1-\frac1{(i+2)^2}$. In case (a) find $\mu_0$ and the stationary distribution.
Structure $0\to1\to2\to\cdots$ and every state leads back to $0$, so the chain is irreducible (and aperiodic, since $p_{00}=1-p_0\gt0$). Starting at $0$, the chain has not returned by time $n$ exactly when its first $n$ steps are all "up": $P_0(T_0\gt n)=p_0p_1\cdots p_{n-1}$. Hence $f_{00}=1-\lim_n\prod_{k\lt n}p_k$ and $\mu_0=\sum_{n\ge0}P_0(T_0\gt n)=\sum_{n\ge0}\prod_{k\lt n}p_k$ (the tail formula of §1.3).
(a) Positive recurrent The product telescopes: $\prod_{k=0}^{n-1}\left(\frac{k+1}{k+2}\right)^2=\frac1{(n+1)^2}\to0$, so the chain is recurrent, and $\mu_0=\sum_{n\ge0}\frac1{(n+1)^2}=\frac{\pi^2}{6}\approx1.645\lt\infty$. By Theorem 3.19, $\pi_0=\frac6{\pi^2}\approx0.608$. The balance equation at $n\ge1$ is $\pi_n=\pi_{n-1}p_{n-1}$, so $\pi_n=\pi_0\prod_{k\lt n}p_k=\frac{6}{\pi^2(n+1)^2}$, which indeed sums to $1$.
(b) Null recurrent $\prod_{k\lt n}\frac{k+1}{k+2}=\frac1{n+1}\to0$: recurrent. But $\mu_0=\sum_n\frac1{n+1}=\infty$: null recurrent, and there is no stationary distribution (the only candidate, $\pi_n\propto\frac1{n+1}$, cannot be normalised).
(c) Transient $\prod_{k=0}^{n-1}\left(1-\frac1{(k+2)^2}\right)=\prod_{m=2}^{n+1}\frac{(m-1)(m+1)}{m^2}=\frac12\cdot\frac{n+2}{n+1}\to\frac12$. So $P_0(T_0=\infty)=\frac12$, $f_{00}=\frac12$, and the chain is transient.
Lesson One family of chains shows all three behaviours: whether the chain is positive recurrent, null recurrent or transient depends on how fast $p_i\to1$.

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.

📐 Theorem 3.20 — Convergence theorem
Let $P$ be irreducible and aperiodic with a stationary distribution $\pi$ (equivalently, irreducible, aperiodic and positive recurrent). Then for every initial distribution $\lambda$, $$P(X_n=j)\to\pi_j\ \text{ for all }j,\qquad\text{indeed}\qquad\sum_{j\in S}\left|P(X_n=j)-\pi_j\right|\to0.$$ In particular $p_{ij}^{(n)}\to\pi_j=1/\mu_j$ for all $i,j$; for finite $S$ this says $P^n\to\mathbf 1\pi$, the matrix all of whose rows equal $\pi$.

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.

📐 Theorem 3.21 — Periodic, null and transient chains; the ergodic theorem

Let $P$ be irreducible.

  1. If $P$ is transient or null recurrent, then $p_{ij}^{(n)}\to0$ for all $i,j$.
  2. 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$.
  3. (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. ∎

📐 Theorem 3.22 — Geometric rate for finite chains
Let $S$ be finite with $s$ states, and suppose that for some $m\ge1$ and $\delta\gt0$ every entry of $P^m$ is at least $\delta$ (by Theorem 3.12(b) this holds for every irreducible aperiodic finite chain). Then for all $i$ and $n$, $$\sum_{j}\left|p_{ij}^{(n)}-\pi_j\right|\le2\,(1-s\delta)^{\lfloor n/m\rfloor}.$$ If $P$ is diagonalisable with eigenvalues $1=\lambda_1,\lambda_2,\dots,\lambda_s$ and $\beta=\max_{k\ge2}|\lambda_k|\lt1$, then $p_{ij}^{(n)}-\pi_j=O(\beta^n)$.

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$.

Interactive 1 — Watching $\lambda P^n$ Converge (or Not)

The chain starts at the chosen state ($\lambda=\delta_i$). The left panel shows the distribution of $X_n$, the row $i$ of $P^n$ (blue bars), against the stationary distribution $\pi$ (purple ticks). The right panel plots the total variation distance $d_n=\frac12\sum_j|p_{ij}^{(n)}-\pi_j|$ on a logarithmic scale (red), together with the line $\beta^n$, where $\beta$ is the second-largest eigenvalue modulus (green dashed). Aperiodic chains converge geometrically with slope set by $\beta$; the periodic Ehrenfest chain never converges ($\beta=1$); the "two rooms" chain converges, but slowly.

n—
d_TV(λPⁿ, π)—
β (second eigenvalue modulus)—
π—
✏️ Example 3 — The Ehrenfest urn: equilibrium without convergence
$N$ molecules are distributed between two halves of a box; at each step one molecule, chosen uniformly at random, moves to the other half. Let $X_n$ be the number in the left half, so $p_{i,i-1}=\frac iN$ and $p_{i,i+1}=\frac{N-i}N$. (a) Find the stationary distribution. (b) Does $p_{00}^{(n)}$ converge? Find $\lim_np_{00}^{(2n)}$. (c) For $N=10$, how long on average does it take a box that starts with all molecules on the right to return to that state? What is the long-run fraction of time with exactly $5$ molecules on each side?
(a) Guess and check Each molecule should be equally likely to be on either side, independently, which suggests $\pi_i=\binom Ni2^{-N}$. Check the detailed balance equations (Definition 3.9 below), which imply stationarity: $\pi_ip_{i,i+1}=\binom Ni2^{-N}\frac{N-i}N=\binom{N-1}{i}2^{-N}$ and $\pi_{i+1}p_{i+1,i}=\binom N{i+1}2^{-N}\frac{i+1}N=\binom{N-1}{i}2^{-N}$. They agree, so $\pi=\operatorname{Bin}(N,\frac12)$, and since the chain is finite and irreducible this is the only stationary distribution (Theorem 3.19).
(b) Periodic Every step changes $X_n$ by $\pm1$, so the chain has period $2$ and $p_{00}^{(n)}=0$ for odd $n$: no convergence. By Theorem 3.21(2), $p_{00}^{(2n)}\to2\pi_0=2^{1-N}$. For $N=4$: $p_{00}^{(2n)}\to\frac18$, and the row $0$ of $P^{40}$ is $(0.125,0,0.75,0,0.125)$ while that of $P^{41}$ is $(0,0.5,0,0.5,0)$. Each is twice $\pi=(\frac1{16},\frac14,\frac38,\frac14,\frac1{16})$ restricted to the even or the odd states.
(c) Return times $\mu_0=1/\pi_0=2^{N}=1024$ steps for $N=10$. The long-run fraction of time at $5$ is $\pi_5=\binom{10}5/1024=\frac{252}{1024}\approx0.246$ (ergodic theorem). For a real gas with $N\approx10^{23}$ the return time $2^N$ is astronomically large. This is how Ehrenfest's model reconciles reversible dynamics (every state recurs) with the irreversible behaviour we observe.
✏️ Example 4 — A reducible chain: many equilibria, limits that depend on the start
For the chain on $\{1,\dots,6\}$ of Example 5 in §3.1 (transient class $\{1,2\}$, closed classes $\{3,4\}$ with period $2$ and $\{5,6\}$ aperiodic, absorption probabilities $\frac13$ and $\frac23$ from states $1,2$), find (a) all stationary distributions; (b) $\lim_np_{15}^{(n)}$ and $\lim_np_{55}^{(n)}$; (c) the Cesàro limits $\lim_n\frac1n\sum_{k=1}^np_{1j}^{(k)}$ for all $j$.
(a) A stationary distribution vanishes on the transient states $1,2$ (Theorem 3.15(2)), and restricted to each closed class it is a multiple of that class's own stationary distribution. On $\{3,4\}$ (the flip chain) it is $(\frac12,\frac12)$. On $\{5,6\}$, with rows $(\frac13,\frac23)$ and $(\frac12,\frac12)$, Theorem 3.3 gives $\left(\frac{1/2}{2/3+1/2},\frac{2/3}{2/3+1/2}\right)=(\frac37,\frac47)$. So the stationary distributions are exactly $t\,(0,0,\frac12,\frac12,0,0)+(1-t)\,(0,0,0,0,\frac37,\frac47)$, $0\le t\le1$: infinitely many.
(b) Inside $\{5,6\}$ the chain is irreducible and aperiodic, so $p_{55}^{(n)}\to\frac37$. From $1$ the chain enters $\{5,6\}$ with probability $\frac23$, and then converges there, so $p_{15}^{(n)}\to\frac23\cdot\frac37=\frac27$. (Formally: condition on the absorption time and class, and use dominated convergence.)
(c) $p_{13}^{(n)}$ does not converge ($\{3,4\}$ is periodic), but its Cesàro averages converge to $f_{13}\pi_3=\frac13\cdot\frac12=\frac16$. Altogether the Cesàro limit of row $1$ is $(0,0,\frac16,\frac16,\frac27,\frac8{21})$, which is the stationary distribution with $t=\frac13$. Numerically, the average of the first $20\,000$ powers gives $(0.0001,0.0001,0.1666,0.1666,0.2857,0.3809)$.
Lesson For reducible chains, $\lim P^n$ (when it exists) has rows that depend on the starting state, through the absorption probabilities. The equality "all rows of $P^n$ tend to the same $\pi$" needs irreducibility, or at least a single closed class, as well as aperiodicity.

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.

📐 Theorem 3.23 — Doubly stochastic matrices
A stochastic matrix is doubly stochastic if its column sums are also $1$: $\sum_ip_{ij}=1$ for every $j$. (a) For finite $S$ with $s$ states, the uniform distribution $(\frac1s,\dots,\frac1s)$ is stationary if and only if $P$ is doubly stochastic. (b) If $P$ is also irreducible, the uniform distribution is the unique stationary distribution and $\mu_i=s$ for every $i$. (c) An irreducible doubly stochastic chain on a countably infinite state space is never positive recurrent.

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. ∎

📘 Definition 3.9 — Detailed balance and reversibility
A measure $\lambda$ is in detailed balance with $P$ if $$\lambda_i\,p_{ij}=\lambda_j\,p_{ji}\qquad\text{for all }i,j\in S.$$ A chain with stationary distribution $\pi$ is reversible if $\pi$ is in detailed balance with $P$. In words: in equilibrium, the probability flow from $i$ to $j$ equals the flow from $j$ to $i$, for every pair separately (not only in total).
📐 Theorem 3.24 — Detailed balance and time reversal
(a) If $\lambda$ is in detailed balance with $P$, then $\lambda$ is invariant; if moreover $\sum_i\lambda_i=1$, it is a stationary distribution.
(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$.

📐 Theorem 3.25 — Kolmogorov's criterion
An irreducible positive recurrent chain is reversible if and only if, for every finite cycle of states $i_0,i_1,\dots,i_{n-1},i_n=i_0$, $$p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{n-1}i_0}=p_{i_0i_{n-1}}p_{i_{n-1}i_{n-2}}\cdots p_{i_1i_0},$$ i.e. every cycle has the same probability traversed in either direction.

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$. ∎

📐 Theorem 3.26 — Random walks on graphs
Let $G$ be a finite connected graph with symmetric edge weights $w_{ij}=w_{ji}\ge0$ (with $w_{ij}\gt0$ iff $\{i,j\}$ is an edge), let $w_i=\sum_jw_{ij}$ and $W=\sum_iw_i$. The random walk $p_{ij}=w_{ij}/w_i$ is irreducible and reversible, with stationary distribution $$\pi_i=\frac{w_i}{W},\qquad\mu_i=\frac{W}{w_i}.$$ For the simple random walk (all weights $1$) this reads $\pi_i=\dfrac{\deg i}{2|E|}$ and $\mu_i=\dfrac{2|E|}{\deg i}$.

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.

✏️ Example 5 — A king wandering on a chessboard
A king moves on an empty $8\times8$ chessboard, at each step to one of the squares it attacks, chosen uniformly at random. Starting from a corner, find the expected number of moves until it first returns to that corner. What fraction of its time does it spend on the four central squares in the long run? Does $P(X_n=\text{corner})$ converge?
Model A simple random walk on the "king graph", whose $64$ vertices are joined when the squares are a king's move apart. It is connected, so Theorem 3.26 applies: $\pi_i=\deg i/\sum_k\deg k$.
Degrees Corners have $3$ neighbours ($4$ squares), other edge squares $5$ ($24$ squares), interior squares $8$ ($36$ squares). Total $\sum\deg=4\cdot3+24\cdot5+36\cdot8=12+120+288=420$ ($=2|E|$, so the graph has $210$ edges).
Return time $\mu_{\text{corner}}=\frac{420}{3}=140$ moves. The four central squares have degree $8$ each, so they are occupied a fraction $\frac{4\cdot8}{420}=\frac{8}{105}\approx7.6\%$ of the time, against $\frac{4}{64}=6.25\%$ for a uniform choice. The walk favours well-connected squares.
Convergence The graph contains triangles (for example a1, b1, a2), which are odd cycles, so the walk is aperiodic (§3.1, Exercise II.5). By Theorem 3.20, $P(X_n=\text{corner})\to\frac3{420}=\frac1{140}$. (For a knight the analogous computation gives $\sum\deg=336$ and $\mu_{\text{corner}}=168$, but the knight graph is bipartite, since every knight move changes the colour of the square, so the knight's walk has period $2$ and $P(X_n=\text{corner})$ does not converge.)
✏️ Example 6 — Reversible or not?
Prove or disprove: (a) the chain on the cycle $\{0,1,2\}$ that moves clockwise ($i\to i+1\bmod 3$) with probability $p$ and anticlockwise with probability $1-p$ is reversible for every $p\in(0,1)$; (b) every irreducible birth–death chain on $\{0,1,\dots,N\}$ (only moves to neighbouring states or staying put) is reversible; (c) every irreducible chain with a symmetric transition matrix on a finite set is reversible, with uniform stationary distribution; (d) a chain with uniform stationary distribution is reversible.
(a) False $P$ is doubly stochastic, so $\pi$ is uniform (Theorem 3.23). Kolmogorov's criterion on the cycle $0\to1\to2\to0$: clockwise probability $p^3$, anticlockwise $(1-p)^3$; equal iff $p=\frac12$. Directly, $\pi_0p_{01}=\frac p3\ne\frac{1-p}3=\pi_1p_{10}$ when $p\ne\frac12$. In equilibrium there is a net circulation around the triangle, and a film of the chain played backwards would rotate the other way: the reversed chain has $\hat P=P^{\mathsf T}$.
(b) True A birth–death chain has no cycles other than back-and-forth ones along a path, for which Kolmogorov's criterion holds trivially. Directly: the flow across the "cut" between $\{0,\dots,i\}$ and $\{i+1,\dots,N\}$ must vanish in equilibrium, and the only transitions across it are $i\to i+1$ and $i+1\to i$, so $\pi_ip_{i,i+1}=\pi_{i+1}p_{i+1,i}$ (see Theorem 3.27).
(c) True With $\pi$ uniform, $\pi_ip_{ij}=\frac{p_{ij}}{s}=\frac{p_{ji}}{s}=\pi_jp_{ji}$. A symmetric stochastic matrix is automatically doubly stochastic.
(d) False The chain of (a) with $p\ne\frac12$ has uniform $\pi$ and is not reversible. For a uniform $\pi$, reversibility is the same as symmetry of $P$.

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.

📐 Theorem 3.27 — Birth–death chains on $\{0,1,2,\dots\}$

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}.$$
  1. 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.
  2. 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$. ∎

✏️ Example 7 — The reflecting random walk: three regimes
On $\{0,1,2,\dots\}$ let $p_{i,i+1}=p$ for all $i\ge0$, $p_{i,i-1}=q=1-p$ for $i\ge1$ and $p_{00}=q$ (a discrete-time queue: an arrival with probability $p$, otherwise a departure if anyone is waiting). Classify the chain for all $p\in(0,1)$. For $p\lt\frac12$ find $\pi$, the mean return time to $0$ and the long-run mean of $X_n$; evaluate them for $p=0.3$.
Series With $\rho=\frac pq$: $\theta_n=\left(\frac pq\right)^n=\rho^n$ and $\rho_n=\left(\frac qp\right)^n=\rho^{-n}$.
Classification $p\lt q$: $\sum\rho^n\lt\infty$, so the chain is positive recurrent. $p=q=\frac12$: both series diverge, so it is null recurrent. $p\gt q$: $\sum\rho^{-n}\lt\infty$, so it is transient, and from $i$ it hits $0$ with probability $\sum_{m\ge i}\rho^{-m}/\sum_{m\ge0}\rho^{-m}=(q/p)^i$, the infinite-casino ruin probability of §3.1.
Equilibrium For $p\lt q$, $\pi_n=(1-\rho)\rho^n$: a geometric distribution on $\{0,1,\dots\}$. So $\mu_0=\frac1{1-\rho}=\frac{q}{q-p}$ and $E_\pi(X)=\frac{\rho}{1-\rho}=\frac{p}{q-p}$.
Numbers $p=0.3$: $\rho=\frac37$, $\pi_0=\frac47\approx0.571$, $\mu_0=\frac74=1.75$ steps, long-run mean queue length $\frac{3/7}{4/7}=0.75$. As $p\uparrow\frac12$, $\pi_0\to0$ and the mean queue length blows up like $\frac{p}{q-p}$, the discrete forerunner of the M/M/1 formula $\frac{\rho}{1-\rho}$ of §9.3. Interactive 2 simulates all three regimes.
Interactive 2 — Positive Recurrent, Null Recurrent or Transient? A Birth–Death Chain

The reflecting walk of Example 7 (up with probability $p$, down or stay at $0$ with probability $q$) runs for $6000$ steps with a seeded generator. The left panel shows the path $X_n$; the right panel shows the fraction of time spent at each state (blue) against $\pi_n=(1-\rho)\rho^n$ (purple) when it exists. Readouts compare the observed fraction of time at $0$ and the mean length of the excursions from $0$ with $\pi_0$ and $\mu_0=1/\pi_0$. For $p\lt\frac12$ they agree, as the ergodic theorem says. At $p=\frac12$ the excursions get longer and longer and the fraction of time at $0$ slowly sinks towards $0$ (null recurrence). For $p\gt\frac12$ the walk escapes and stops returning (transience).

0.35
steps n—
regime—
time at 0: observed / π₀—
mean excursion from 0: observed / μ₀—
⚠️ Counterexamples and pitfalls
  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.
  2. 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).
  3. 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.
  4. 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.
  5. $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.
  6. 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.
  7. 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.
  8. 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$.
  9. 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.
  10. 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.
  11. Bipartite graphs give periodic walks. The knight's walk and the walk on a cube have stationary distributions $\propto$ degree but period $2$.

Exercises

I
Finding stationary distributions.
  • 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.
Check lab: stationary distribution of a $3\times3$ chain

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/πᵢ—
doubly stochastic?—
detailed balance?—
1 Theorem 3.3 of §3.1 with $a=0.8$, $b=0.6$: $\pi=\left(\frac{0.6}{1.4},\frac{0.8}{1.4}\right)=\left(\frac37,\frac47\right)$, $\mu=\left(\frac73,\frac74\right)$, and since $|1-a-b|=0.4\lt1$, $P^n\to\begin{pmatrix}\frac37&\frac47\\\frac37&\frac47\end{pmatrix}$ (with error $\propto0.4^n$, alternating in sign).
2 $P$ is symmetric, hence doubly stochastic: $\pi=(\frac13,\frac13,\frac13)$. Write $P=\frac12(J-I)$ with $J$ the all-ones matrix. Since $J^2=3J$, $P$ has eigenvalue $1$ on $\mathbf 1$ and $-\frac12$ on vectors with zero sum, so $P^n=\frac13J+\left(-\frac12\right)^n\left(I-\frac13J\right)$ and $p_{11}^{(n)}=\frac13+\frac23\left(-\frac12\right)^n$. (Check: $n=2$ gives $\frac12$, $n=3$ gives $\frac14$.)
3 Every column also sums to $1$: the matrix is doubly stochastic and irreducible ($1\to2\to3\to1$), so $\pi$ is uniform (Theorem 3.23).
4 $\{1,2\}$ and $\{4\}$ are closed, and $3$ is transient, so $\pi_3=0$. On $\{1,2\}$ the stationary law is $(\frac12,\frac12)$. All stationary distributions: $t(\frac12,\frac12,0,0)+(1-t)(0,0,0,1)$, $0\le t\le1$.
5 $\pi Q=\frac12(\pi+\pi P)=\pi$. $Q$ has the same off-diagonal arrows as $P$ (plus self-loops), so it is irreducible, and $q_{ii}\ge\frac12\gt0$ makes it aperiodic. Lazy versions are the standard way to remove periodicity without changing the equilibrium.
6 The matrix is doubly stochastic (each state receives $p$ from its left neighbour and $1-p$ from its right one), so $\pi$ is uniform, $\pi_i=\frac1m$. Each step changes the state by $\pm1$. If $m$ is even, the parity of the state alternates, so the period is $2$. If $m$ is odd, there are returns of length $2$ (forth and back) and of length $m$ (once round), and $\gcd(2,m)=1$, so the chain is aperiodic.
7 $\pi=\left(\frac b{a+b},\frac a{a+b}\right)=\left(\frac13,\frac23\right)$ iff $a=2b$, with $0\lt b\le\frac12$. Convergence holds iff $|1-a-b|=|1-3b|\lt1$, i.e. always except $b=\frac23$, which is not allowed. So all these chains converge. (The only non-convergent two-state chain, $a=b=1$, has $\pi=(\frac12,\frac12)$.)
8 Balance: $\pi_0=\frac12\pi_3$, $\pi_1=\pi_0+\frac12\pi_3$, $\pi_2=\pi_1$, $\pi_3=\pi_2$. So $\pi_1=\pi_2=\pi_3=c$, $\pi_0=\frac c2$, and $\frac72c=1$: $\pi=\left(\frac17,\frac27,\frac27,\frac27\right)$, $\mu_0=7$. Directly: from $0$ the chain needs $4$ steps to come back via $3\to0$; each time it chooses $3\to1$ instead, the loop $1\to2\to3$ adds $3$ steps. The number of such detours is geometric with mean $1$, so $E_0(T_0)=4+3\cdot1=7$.
II
Limits, periodicity and the ergodic theorem.
  • 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 The limit is $\pi_R=\frac{15}{61}\approx0.246$ (Theorem 3.20). The largest error $\max_{i,j}|p_{ij}^{(n)}-\pi_j|$ is $0.00148$ at $n=6$ and $0.00055$ at $n=7$, so $n=7$. The ratio of successive errors is close to $\beta=\frac{2+\sqrt3}{10}\approx0.373$.
2 $\pi=(\frac1{16},\frac14,\frac38,\frac14,\frac1{16})$ and the period is $2$, so by Theorem 3.21(2), $p_{00}^{(2n)}\to2\pi_0=\frac18$ and $p_{01}^{(2n+1)}\to2\pi_1=\frac12$. The Cesàro limit is $\pi_0=\frac1{16}$ (half the time the probability is $0$).
3 By the ergodic theorem, the long-run fractions of working and repair days are $\pi=(\frac67,\frac17)$. Average profit: $100\cdot\frac67-400\cdot\frac17=\frac{200}7\approx28.57$ rupees per day.
4 $m=10$. A first return to $0$ takes $4$ steps plus $3$ for each detour $3\to1\to2\to3$, so first-return times are $4,7,10,\dots$; general return times are sums of these. A direct computation of the powers shows that $P^9$ still has a zero entry while every entry of $P^{10}$ is positive. This equals Wielandt's bound $(4-1)^2+1=10$: this chain is the extremal example.
5 From Theorem 3.3 of §3.1, $p_{11}^{(n)}-\pi_1=\frac{a}{a+b}\alpha^n$ and $p_{12}^{(n)}-\pi_2=-\frac a{a+b}\alpha^n$, with $\alpha=1-a-b$. So $\frac12\sum_j|p_{1j}^{(n)}-\pi_j|=\frac a{a+b}|\alpha|^n$.
6 If aperiodic, Theorem 3.20 applies (a finite irreducible chain is positive recurrent). Conversely, if $d\ge2$, then $p_{ii}^{(n)}=0$ whenever $d\nmid n$, while $p_{ii}^{(nd)}\to d\pi_i\gt0$ (Theorem 3.21(2)); so $p_{ii}^{(n)}$ does not converge.
7 By Theorem 3.18, $\gamma^i$ (expected visits during an excursion from $i$) equals $\pi/\pi_i$, since $\pi/\pi_i$ is invariant with value $1$ at $i$. Weather: $\pi_R/\pi_S=\frac{15/61}{24/61}=\frac58$ rainy days between consecutive sunny days, on average.
8 Theorem 3.26: degrees $1,2,2,1$, so $\pi=(\frac16,\frac13,\frac13,\frac16)$. The path is bipartite, so the period is $2$ and $p_{11}^{(2n)}\to2\pi_1=\frac13$. Numerically, row $1$ of $P^{100}$ is $(\frac13,0,\frac23,0)$.
III
Doubly stochastic matrices, reversibility and random walks on graphs.
  • 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 The biased cycle with $p=\frac23$: rows $(0,\frac23,\frac13)$, $(\frac13,0,\frac23)$, $(\frac23,\frac13,0)$. Its columns sum to $1$, so $\pi$ is uniform; since $P$ is not symmetric, detailed balance with uniform $\pi$ fails: not reversible.
2 The cube is $3$-regular with $8$ vertices: $\pi_v=\frac18$, $\mu_v=8$. It is bipartite (by the parity of the number of $1$s in the coordinates), so the period is $2$ and $p_{vv}^{(n)}$ alternates between $0$ and values tending to $\frac14$.
3 Summing the knight's degrees over the $64$ squares gives $336$, and a corner has degree $2$, so $\mu=\frac{336}2=168$ and the long-run fraction of time at that corner is $\frac1{168}$. Every knight move changes the colour of the square, so the walk has period $2$ and $P(X_n=\text{corner})=0$ for all odd $n$.
4 $\pi_1p_{12}=\frac14\cdot\frac12=\frac18=\frac12\cdot\frac14=\pi_2p_{21}$; $\pi_2p_{23}=\frac18=\pi_3p_{32}$; $\pi_1p_{13}=0=\pi_3p_{31}$. Detailed balance holds, so $\pi$ is stationary (and the chain is reversible).
5 Cycle $1\to2\to3\to1$: $\frac12\cdot\frac23\cdot\frac14=\frac1{12}$; reversed $1\to3\to2\to1$: $\frac12\cdot\frac34\cdot\frac13=\frac18$. These differ: not reversible. Global balance: $\pi_1=\frac13\pi_2+\frac14\pi_3$, $\pi_2=\frac12\pi_1+\frac34\pi_3$, with $\sum\pi_i=1$, gives $\pi=\left(\frac{12}{53},\frac{21}{53},\frac{20}{53}\right)$. (Check the third equation: $\frac12\cdot\frac{12}{53}+\frac23\cdot\frac{21}{53}=\frac{6+14}{53}=\frac{20}{53}$.)
6 For $i\ne j$: $\pi_ip_{ij}=q_{ij}\min(\pi_i,\pi_j)$, which is symmetric in $i,j$ because $q_{ij}=q_{ji}$. So detailed balance holds; $p_{ii}\ge0$ because $\sum_{j\ne i}p_{ij}\le\sum_jq_{ij}\le1$. This is why Markov chain Monte Carlo needs $\pi$ only up to a constant: only the ratios $\pi_j/\pi_i$ appear.
7 $\pi$ is uniform, so $\hat p_{ij}=\pi_jp_{ji}/\pi_i=p_{ji}$: $\hat P=P^{\mathsf T}$, the cycle run with clockwise probability $1-p$. The film run backwards circulates the other way.
8 $w_1=1+2=3$, $w_2=1+3=4$, $w_3=2+3=5$, $W=12$. $P$ has rows $(0,\frac13,\frac23)$, $(\frac14,0,\frac34)$, $(\frac25,\frac35,0)$, and $\pi=(\frac3{12},\frac4{12},\frac5{12})=(\frac14,\frac13,\frac5{12})$ (Theorem 3.26).
IV
Countable state spaces and birth–death chains.
  • 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.
1 $\rho=\frac{0.25}{0.75}=\frac13$: $\pi_n=\frac23\left(\frac13\right)^n$, $\mu_0=\frac32$, $E_\pi X=\frac{\rho}{1-\rho}=\frac12$.
2 From Example 2, $\pi_n=\pi_0p^n$, so $\pi_n=(1-p)p^n$ and $\mu_0=\frac1{1-p}$ (also directly: $T_0$ is geometric with $P_0(T_0\gt n)=p^n$). The chain is aperiodic ($p_{00}\gt0$), so $P(X_n=0)\to1-p$.
3 $q_k/p_k=\frac{k}{k+1}$, so $\rho_n=\frac1{n+1}$ and $\sum\rho_n=\infty$: recurrent. $\theta_n=\frac{p_0\cdots p_{n-1}}{q_1\cdots q_n}$; since $\frac{p_{k-1}}{q_k}=\frac{k/(2k-1)}{k/(2k+1)}=\frac{2k+1}{2k-1}$ for $k\ge2$ and $\frac{p_0}{q_1}=3$, the product telescopes to $\theta_n=2n+1$. $\sum\theta_n=\infty$: null recurrent.
4 $\lambda P$ at $j$ is $p\lambda_{j-1}+q\lambda_{j+1}$. For $\lambda\equiv1$ this is $p+q=1$. For $\lambda_i=r^i$ with $r=p/q$ it is $r^{j-1}(p+qr^2)=r^{j-1}\left(p+\frac{p^2}{q}\right)=r^{j-1}\cdot\frac pq=r^j$. Theorem 3.18's uniqueness needs recurrence, and this walk is transient.
5 $\theta_n=\frac{p^n}{q^n}$, so the chain is positive recurrent iff $p\lt q$, and then $\pi_n=\left(1-\frac pq\right)\left(\frac pq\right)^n$. The holding probabilities $1-p-q$ do not enter: detailed balance only involves the flows $\pi_np=\pi_{n+1}q$.
6 $\theta_n=\frac{p_0\cdots p_{n-1}}{q_1\cdots q_n}=\frac{1/(n+1)!}{2/(n+2)}=\frac{n+2}{2\,(n+1)!}$. Then $\sum_n\theta_n=\frac12\sum_{m\ge1}\frac{m+1}{m!}=\frac12\left(e+(e-1)\right)=\frac{2e-1}{2}\lt\infty$: positive recurrent, with $\pi_0=\frac2{2e-1}\approx0.4508$.
7 $\theta_0=1$, $\theta_n=\frac{1\cdot p^{n-1}}{q^n}$ for $n\ge1$, so $\sum\theta_n=1+\frac1q\cdot\frac1{1-p/q}=1+\frac1{q-p}$, and $\pi_0=\frac{q-p}{1+q-p}=\frac{q-p}{2q}$. Each step changes the state by $\pm1$, so the period is $2$, and $p_{00}^{(2n)}\to2\pi_0=\frac{q-p}{q}$. (For $p=\frac13$: $\pi_0=\frac14$ and $p_{00}^{(2n)}\to\frac12$.)
8 By Theorem 3.18 every invariant measure is a multiple of $\gamma^k$, so $\lambda=c\gamma^k$ with $c=\lambda_k\gt0$. Hence $\mu_k=\sum_i\gamma_i^k=\frac1c\sum_i\lambda_i=\infty$, for every $k$.
🎯 Exam corner CSIR Part BCSIR Part CGATE ST

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$.

Idea The chain is finite and irreducible, so $\mu_1=1/\pi_1$ (Theorem 3.19).
Solve $\pi_1=\frac13\pi_2$; $\pi_3=\frac13\pi_2+\frac12\pi_3$, so $\pi_3=\frac23\pi_2$. Then $\pi\propto(\frac13,1,\frac23)$, i.e. $\pi=(\frac16,\frac12,\frac13)$ (check $\pi_2=\pi_1+\frac13\pi_2+\frac12\pi_3=\frac16+\frac16+\frac16$).
Answer (C) $\mu_1=6$.

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.

Idea Positive entries give irreducibility and aperiodicity; doubly stochastic gives uniform $\pi$ (Theorem 3.23).
Conclusion By Theorem 3.20, $p_{31}^{(n)}\to\pi_1=\frac14$. (D) would be right without the positivity assumption: the doubly stochastic permutation matrix of a $4$-cycle is periodic.
Answer (B).

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$.

Degrees The hub has degree $5$; each rim vertex has degree $3$ (two rim neighbours and the hub). $\sum\deg=5+5\cdot3=20=2|E|$.
Formula $\mu_{\text{hub}}=\frac{2|E|}{\deg(\text{hub})}=\frac{20}5=4$ (Theorem 3.26). Option (D) is the return time to a rim vertex.
Answer (A).

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.

(A) True Theorem 3.16 (Cesàro averages and compactness).
(B) False The flip chain $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ is irreducible, but $P^n$ alternates between $I$ and $P$. Aperiodicity is also needed.
(C) True The set of stationary distributions is convex (Theorem 3.15(3)).
(D) False The symmetric walk on $\mathbb{Z}$ (null recurrent) has none.
Answer (A) and (C).

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.

Series With $q=1-p$: $\theta_0=1$, $\theta_n=\frac{p^{n-1}}{q^n}$ ($n\ge1$), $\rho_n=\left(\frac qp\right)^n$ (Theorem 3.27).
(A) True $p=\frac13$, $q=\frac23$: $\sum\theta_n=1+\frac1q\cdot\frac1{1-p/q}=1+\frac32\cdot2=4$, so $\pi_0=\frac14$. (The chain has period $2$, so $\pi$ exists although $P^n$ does not converge.)
(B) True, (C) False $p=q$: $\sum\rho_n=\sum1=\infty$ (recurrent) and $\theta_n=2$ for $n\ge1$, so $\sum\theta_n=\infty$ (no stationary distribution): null recurrent, $\mu_0=\infty$.
(D) False $p=\frac23$: $\sum\rho_n=\sum2^{-n}\lt\infty$, so the chain is transient.
Answer (A) and (B).

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}$.

(A) True Every column sums to $1$ (doubly stochastic), and the chain is irreducible, so $\pi$ is uniform and unique (Theorem 3.23).
(B) False $\pi_1p_{12}=\frac29\ne\frac19=\pi_2p_{21}$; equivalently the cycle $1\to2\to3\to1$ has probability $\frac8{27}$ one way and $\frac1{27}$ the other.
(C) True Returns of length $2$ ($1\to2\to1$) and $3$ ($1\to2\to3\to1$) give period $\gcd(2,3)=1$; Theorem 3.20 gives $p_{12}^{(n)}\to\frac13$.
(D) True $\hat p_{ij}=\pi_jp_{ji}/\pi_i=p_{ji}$ for uniform $\pi$ (Theorem 3.24(b)).
Answer (A), (C) and (D).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. 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.
  2. 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.
  3. 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–Teaching NexusResearch-tutored · optional, about 45 minutes

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.

  1. 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.
  2. 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).
  3. 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$.
  4. 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.

Instructor note: in $H$, the pages D and E form a transient class and $\{A,B,C\}$ is closed and aperiodic (cycles A→C→A of length 2 and A→B→C→A of length 3), so the unique stationary distribution of $H$ is $(0.4,0.2,0.4,0,0)$: D and E get rank zero, which is unsatisfactory. With $d=0.85$ the PageRank vector is approximately A $0.344$, B $0.191$, C $0.353$, D $0.068$, E $0.044$. C has the most in-links (three) and ranks first, but A, with two in-links, nearly ties with it because one of them comes from the heavily visited C. The $\ell^1$ error of the power method is about $1.3\times10^{-2}$, $9.7\times10^{-4}$, $4.1\times10^{-6}$ and $1.5\times10^{-10}$ after $5$, $10$, $20$ and $40$ steps, decaying like $\beta^k$ with $\beta\approx0.601\le d$.

🧪 Self-check quiz

0/5 correct

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