n-Step Transition Limits and Stationary Distributions
CSIR NET statistics: stationary distributions, mean recurrence times, the convergence theorem for P^n, periodic and reducible chains, detailed balance.
- 20 min
On this page · 13 sections
Prerequisites
- Markov Chains and Classification of States: classes, recurrence, period and absorption probabilities are all used below.
- Eigenvalues and the Cayley–Hamilton Theorem: a stationary distribution is a left eigenvector for eigenvalue 1.
- Change of Basis and Canonical Forms: diagonalising \( P \) gives \( P^n \) in closed form.
The Hook: The Chain That Forgets
Stationary Distributions
A row vector \( \pi = (\pi_j)_{j \in S} \) is a stationary (invariant, equilibrium) distribution for \( P \) if
$$\pi_j \ge 0, \qquad \sum_j \pi_j = 1, \qquad \pi P = \pi, \ \text{ i.e. } \ \pi_j = \sum_i \pi_i p_{ij} \text{ for all } j.$$If \( X_0 \sim \pi \), then \( X_n \sim \pi \) for every \( n \): the chain is then a stationary process.
For a finite chain, \( \pi \) is a left eigenvector of \( P \) for eigenvalue 1 (equivalently, a right eigenvector of \( P^T \)), normalised to sum 1. To compute it, write \( \pi P = \pi \), drop one equation (the \( m \) equations are dependent, because every row of \( P - I \) sums to 0, so \( P - I \) is singular), and add \( \sum \pi_j = 1 \).
Existence and uniqueness
Let \( P \) be irreducible on a finite or countable \( S \). Then
- \( P \) has a stationary distribution if and only if it is positive recurrent;
- in that case the stationary distribution is unique and $$\boxed{\pi_j = \frac{1}{\mu_j} > 0}, \qquad \mu_j = E[T_j \mid X_0 = j] \ \text{(mean recurrence time)}.$$
For a finite irreducible chain both conditions hold automatically: a unique stationary distribution, with every entry positive.
General finite chains. Every finite chain has at least one stationary distribution. If the closed classes are \( C_1, \dots, C_r \) with stationary distributions \( \pi^{(1)}, \dots, \pi^{(r)} \) (each supported on its class), then the stationary distributions of \( P \) are exactly the convex combinations
$$\pi = \sum_{k=1}^{r} c_k\,\pi^{(k)}, \qquad c_k \ge 0, \ \sum c_k = 1.$$So \( \pi_j = 0 \) at every transient state, and the stationary distribution is unique iff there is exactly one closed class. Irreducibility is sufficient for uniqueness, not necessary.
Countable chains. A transient or null recurrent irreducible chain has no stationary distribution. The symmetric walk on \( \mathbb{Z} \) has the invariant measure \( \pi_j = 1 \) (constant), which cannot be normalised.
Shortcuts for Computing π
| Situation | Stationary distribution |
|---|---|
| Two states, \( P = \begin{pmatrix} 1 - a & a \\ b & 1 - b \end{pmatrix} \), \( a + b > 0 \) | \( \pi = \left(\frac{b}{a + b}, \frac{a}{a + b}\right) \) |
| Doubly stochastic, irreducible, \( m \) states | uniform, \( \pi_j = \frac1m \) |
| Detailed balance holds | solve \( \pi_ip_{ij} = \pi_jp_{ji} \) along edges |
| Random walk on a connected graph (step to a uniform neighbour) | \( \pi_v = \frac{\deg v}{2\lvert E \rvert} \) |
| Birth–death chain on \( \{0, 1, 2, \dots\} \) | \( \pi_n = \pi_0\prod_{k=1}^{n}\frac{p_{k-1}}{q_k} \) |
Detailed balance and reversibility
Detailed balance is sufficient, not necessary. The deterministic 3-cycle \( 1 \to 2 \to 3 \to 1 \) has uniform \( \pi \) but \( \pi_1p_{12} = \frac13 \ne 0 = \pi_2p_{21} \). Every birth–death chain (moves only to neighbours on a line) with a stationary distribution satisfies detailed balance, and so does every random walk on an undirected graph.
Birth–death chains on the non-negative integers
Let \( p_{n,n+1} = p_n \), \( p_{n,n-1} = q_n \) (\( q_0 = 0 \)), \( p_{nn} = r_n \), with all \( p_n, q_n > 0 \) where defined. Detailed balance across the edge \( \{n - 1, n\} \) gives \( \pi_{n-1}p_{n-1} = \pi_nq_n \), so
$$\pi_n = \pi_0\prod_{k=1}^{n}\frac{p_{k-1}}{q_k}, \qquad \text{positive recurrent} \iff \sum_{n \ge 0}\prod_{k=1}^{n}\frac{p_{k-1}}{q_k} < \infty.$$Reflecting random walk. \( p_n = p \) for all \( n \ge 0 \), \( q_n = q \) for \( n \ge 1 \), \( p_{00} = q \). With \( r = \frac{p}{q} \): \( \pi_n = \pi_0r^n \), summable iff \( p < q \), and then
$$\pi_n = (1 - r)r^n \quad (\text{geometric}), \qquad \mu_0 = \frac{1}{1 - r}.$$For \( p = q \) the chain is null recurrent; for \( p > q \) it is transient. This is the discrete skeleton of the M/M/1 queue on the next page.
Ehrenfest urn. \( N \) balls in two urns; at each step a uniformly chosen ball switches urns. With \( X_n \) the number in urn 1, \( p_{k,k-1} = \frac{k}{N} \), \( p_{k,k+1} = \frac{N - k}{N} \). Detailed balance gives \( \pi_k = \binom{N}{k}2^{-N} \) (binomial). The chain has period 2. Starting with all balls in one urn, the mean time to return there is \( \frac{1}{\pi_0} = 2^N \).
Limits of n-Step Probabilities
Let \( P \) be irreducible, aperiodic and positive recurrent (an ergodic chain) with stationary distribution \( \pi \). Then for all \( i, j \),
$$\lim_{n \to \infty} p_{ij}^{(n)} = \pi_j = \frac{1}{\mu_j},$$and \( \mu^{(0)}P^n \to \pi \) for every initial distribution. For a finite chain: \( P^n \to \mathbf{1}\pi \), the matrix all of whose rows equal \( \pi \).
What happens when a hypothesis fails:
| Chain | Behaviour of \( p_{ij}^{(n)} \) |
|---|---|
| \( j \) transient | \( \to 0 \) (even \( \sum_n p_{ij}^{(n)} < \infty \)) |
| \( j \) null recurrent | \( \to 0 \), though \( \sum_n p_{jj}^{(n)} = \infty \) |
| irreducible, positive recurrent, period \( d > 1 \) | no limit; \( p_{jj}^{(nd)} \to d\,\pi_j \); Cesàro averages converge |
| \( j \) in an aperiodic positive recurrent class \( C \), any start \( i \) | \( \to h_i(C)\,\pi_j \), where \( h_i(C) = P(\text{absorbed in } C \mid X_0 = i) \) |
For an irreducible positive recurrent chain (any period),
$$\frac1n\sum_{k=1}^{n} p_{ij}^{(k)} \to \pi_j, \qquad \frac1n\#\{k < n : X_k = j\} \to \frac{1}{\mu_j} = \pi_j \ \text{ almost surely}.$$More generally, for bounded \( f \), \( \frac1n\sum_{k=0}^{n-1} f(X_k) \to \sum_j \pi_jf(j) \) almost surely. So \( \pi_j \) is always the long-run fraction of time in \( j \), even when \( p_{ij}^{(n)} \) has no limit.
For \( P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \): \( p_{11}^{(n)} \) is 0 for odd \( n \) and 1 for even \( n \), so there is no limit; the Cesàro averages tend to \( \frac12 = \pi_1 \); and \( p_{11}^{(2n)} = 1 = d\,\pi_1 \) with \( d = 2 \).
Reducible chains
P^n in Closed Form
Two-state chain. With \( P = \begin{pmatrix} 1 - a & a \\ b & 1 - b \end{pmatrix} \), \( 0 < a + b \), the eigenvalues are \( 1 \) and \( \lambda = 1 - a - b \), and
$$P^n = \frac{1}{a + b}\begin{pmatrix} b & a \\ b & a \end{pmatrix} + \frac{(1 - a - b)^n}{a + b}\begin{pmatrix} a & -a \\ -b & b \end{pmatrix}.$$For the weather chain, \( a = 0.3 \), \( b = 0.4 \), \( \lambda = 0.3 \): \( p_{DD}^{(n)} = \frac47 + \frac37(0.3)^n \), giving \( 0.61 \) at \( n = 2 \) and \( 0.583 \) at \( n = 3 \). The error shrinks like \( \lvert \lambda \rvert^n \). Special cases: \( a + b = 1 \) (identical rows) gives \( P^n = P \) at once; \( a = b = 1 \) gives \( \lambda = -1 \), the periodic flip; \( a = b = 0 \) gives \( P = I \), two closed classes.
Spectral facts for a finite stochastic \( P \).
- 1 is an eigenvalue; every eigenvalue has \( \lvert \lambda \rvert \le 1 \).
- The algebraic multiplicity of the eigenvalue 1 equals the number of closed (recurrent) classes.
- For an irreducible \( P \) of period \( d \), the eigenvalues of modulus 1 are exactly the \( d \)-th roots of unity, each simple. In particular \( -1 \) is an eigenvalue of an irreducible chain iff its period is even.
- If \( P \) is ergodic and diagonalisable, \( P^n = \mathbf{1}\pi + \sum_{k \ge 2}\lambda_k^nE_k \); the speed of convergence is set by the second-largest \( \lvert \lambda_k \rvert \).
graph TD
A["Does lim p_ij^(n) exist?"] --> B{"j transient or null recurrent?"}
B -->|Yes| C["Limit 0"]
B -->|No: j positive recurrent| D{"Class of j aperiodic?"}
D -->|No, period d| E["No limit in general;
Cesaro average tends to h_i pi_j"]
D -->|Yes| F["Limit = h_i(C) x pi_j
(h = 1 if i is in C)"]Memory Tricks
- Pi is one over mu. \( \pi_j = \frac{1}{\mu_j} \): a state you visit every 4 steps on average holds a quarter of the time.
- Two-state rule: cross over the sum. \( \pi = \left(\frac{b}{a + b}, \frac{a}{a + b}\right) \): each state’s weight is the rate of flowing into it.
- Graphs pay by degree. Random walk on a graph: \( \pi_v \propto \deg v \); return time \( \frac{2\lvert E \rvert}{\deg v} \).
- IAP for limits. Irreducible, Aperiodic, Positive recurrent: all three, and \( P^n \) forgets the start.
- Columns sum to 1, answer is flat. Doubly stochastic and irreducible means uniform \( \pi \).
Don’t Confuse
| This | Is not this | The difference |
|---|---|---|
| stationary distribution | limiting distribution | the flip chain has \( \pi = (\frac12, \frac12) \) but no limit of \( P^n \) |
| unique \( \pi \) | irreducible | unique iff exactly one closed class; transient states may be present |
| \( \pi P = \pi \) (left eigenvector) | \( P\pi^T = \pi^T \) (right eigenvector) | the right eigenvector for 1 is \( \mathbf{1} \), always |
| detailed balance | stationarity | balance is sufficient, not necessary (the 3-cycle) |
| \( p_{jj}^{(n)} \to 0 \) | \( j \) transient | null recurrent states also have \( p_{jj}^{(n)} \to 0 \) |
| \( \pi_j = \frac{1}{\mu_j} \) | \( \pi_j = \mu_j \) | frequent visits mean large \( \pi_j \), short return times |
| invariant measure | stationary distribution | a measure need not be summable (constant on \( \mathbb{Z} \)) |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C of the Mathematical Sciences paper, one or more options may be correct.
Level 1: Foundation
- An irreducible chain on 5 states has a doubly stochastic transition matrix. What is its stationary distribution?
- In an ergodic chain, \( \pi_3 = 0.25 \). What is the mean recurrence time of state 3?
- Does every finite Markov chain have a stationary distribution?
Answers
- Uniform: \( \pi_j = \frac15 \). The uniform vector satisfies \( \pi P = \pi \) because columns sum to 1, and irreducibility makes it the only one.
- 4. \( \mu_3 = \frac{1}{\pi_3} \).
- Yes, at least one (one for each closed class, and their convex combinations). Uniqueness needs exactly one closed class.
Level 2: Part B Style
Practice Q1. The stationary distribution of
$$P = \begin{pmatrix} \frac12 & \frac12 & 0 \\ \frac13 & \frac13 & \frac13 \\ 0 & \frac12 & \frac12 \end{pmatrix}$$is:
(a) \( \left(\frac13, \frac13, \frac13\right) \) (b) \( \left(\frac27, \frac37, \frac27\right) \) (c) \( \left(\frac14, \frac12, \frac14\right) \) (d) \( \left(\frac38, \frac14, \frac38\right) \)
Answer: (b)
Neighbour moves only, so detailed balance: \( \pi_1 \cdot \frac12 = \pi_2 \cdot \frac13 \Rightarrow \pi_2 = \frac32\pi_1 \); \( \pi_2 \cdot \frac13 = \pi_3 \cdot \frac12 \Rightarrow \pi_3 = \pi_1 \). Then \( \pi_1(1 + \frac32 + 1) = 1 \), \( \pi_1 = \frac27 \). Option (a) assumes \( P \) is doubly stochastic; its middle column sums to \( \frac43 \).
Practice Q2. For \( P = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} \), \( p_{11}^{(3)} \) equals:
(a) 0.343 (b) 0.583 (c) 0.61 (d) \( \frac47 \)
Answer: (b)
\( p_{11}^{(n)} = \frac{b}{a + b} + \frac{a}{a + b}(1 - a - b)^n = \frac47 + \frac37(0.3)^3 = \frac{4 + 0.081}{7} = 0.583 \). Option (a) is \( 0.7^3 \), the probability of staying in state 1 at every step, which ignores paths that leave and come back. Option (c) is \( p_{11}^{(2)} \); (d) is the limit.
Practice Q3. A king performs a random walk on an \( 8 \times 8 \) chessboard, moving at each step to a uniformly chosen legal neighbouring square. Starting from a corner, the expected number of moves until it first returns to that corner is:
(a) 64 (b) 105 (c) 140 (d) 210
Answer: (c)
Random walk on a graph: \( \pi_v = \frac{\deg v}{\sum_u \deg u} \). Degrees: 4 corners \( \times 3 \), 24 edge squares \( \times 5 \), 36 interior squares \( \times 8 \): total 420. \( \mu_{\text{corner}} = \frac{420}{3} = 140 \). Option (d) is \( \lvert E \rvert = 210 \), half the total degree.
Practice Q4. For the five-state chain with
$$P = \begin{pmatrix} \frac12 & \frac12 & 0 & 0 & 0 \\ \frac14 & \frac34 & 0 & 0 & 0 \\ 0 & \frac14 & \frac14 & \frac12 & 0 \\ 0 & 0 & \frac12 & 0 & \frac12 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix},$$\( \lim_{n \to \infty} p_{42}^{(n)} \) is:
(a) \( \frac23 \) (b) \( \frac13 \) (c) \( \frac16 \) (d) \( \frac14 \)
Answer: (c)
From 4, absorption in \( \{1, 2\} \) has probability \( h_4 = \frac14 \) (previous page). Inside \( \{1, 2\} \), \( \pi = \left(\frac13, \frac23\right) \). So the limit is \( \frac14 \cdot \frac23 = \frac16 \). Option (a) forgets the absorption probability; (d) is \( h_4 \) alone.
Level 3: Part C Style
Practice Q5. Let \( P = \begin{pmatrix} 0 & 1 & 0 \\ \frac12 & 0 & \frac12 \\ 0 & 1 & 0 \end{pmatrix} \) (random walk on the path \( 1 - 2 - 3 \)). Which statements are true?
(a) \( P \) has a unique stationary distribution, \( \left(\frac14, \frac12, \frac14\right) \). (b) \( \lim_{n \to \infty} p_{22}^{(n)} = \frac12 \). (c) \( \lim_{n \to \infty}\frac1n\sum_{k=1}^{n}p_{22}^{(k)} = \frac12 \). (d) \( -1 \) is an eigenvalue of \( P \).
Answer: (a), (c) and (d)
- (a) True. Irreducible and finite, so \( \pi \) is unique; random walk on a graph with degrees \( 1, 2, 1 \) gives \( \pi \propto (1, 2, 1) \).
- (b) False. From 2 the chain goes to 1 or 3 and must come straight back, so \( p_{22}^{(n)} = 1 \) for even \( n \) and 0 for odd \( n \). No limit: the chain has period 2.
- (c) True. Cesàro averages of an irreducible positive recurrent chain tend to \( \pi_2 = \frac12 \) (here the averages are \( \frac{\lfloor n/2 \rfloor}{n} \to \frac12 \)).
- (d) True. An irreducible chain of period 2 has the square roots of unity, \( \pm 1 \), as eigenvalues. Directly, the eigenvalues are \( 1, 0, -1 \) (trace 0, and \( P \) has rank 2).
Practice Q6. A Markov chain on \( \{1, 2, 3, 4, 5\} \) has two closed classes, \( \{1, 2\} \) and \( \{4, 5\} \), both aperiodic, and state 3 transient with \( p_{31} > 0 \) and \( p_{34} > 0 \). Which statements are true?
(a) \( P \) has infinitely many stationary distributions. (b) The eigenvalue 1 of \( P \) has algebraic multiplicity 2. (c) Every stationary distribution \( \pi \) has \( \pi_3 = 0 \). (d) \( \lim_n P^n \) exists and all its rows are equal.
Answer: (a), (b) and (c)
- (a) True. If \( \pi^{(1)} \) and \( \pi^{(2)} \) are the stationary distributions of the two closed classes, every \( c\pi^{(1)} + (1 - c)\pi^{(2)} \), \( c \in [0, 1] \), is stationary.
- (b) True. The multiplicity of the eigenvalue 1 equals the number of closed classes.
- (c) True. Stationary distributions vanish on transient states.
- (d) False. The limit exists (both closed classes are aperiodic), but row 1 of the limit is supported on \( \{1, 2\} \) while row 4 is supported on \( \{4, 5\} \). The rows differ.
Practice Q7. On \( \{0, 1, 2, \dots\} \) let \( p_{n,n+1} = \frac13 \) for \( n \ge 0 \), \( p_{n,n-1} = \frac23 \) for \( n \ge 1 \), and \( p_{00} = \frac23 \). Which statements are true?
(a) The chain is positive recurrent. (b) Its stationary distribution has \( \pi_0 = \frac12 \). (c) The mean recurrence time of state 1 is 2. (d) If instead \( p_{n,n+1} = p_{n,n-1} = \frac12 \) (\( n \ge 1 \)), \( p_{01} = p_{00} = \frac12 \), the chain has a stationary distribution.
Answer: (a) and (b)
Reflecting walk with \( r = \frac{p}{q} = \frac12 \): \( \pi_n = (1 - r)r^n = \frac12 \cdot \left(\frac12\right)^n \).
- (a) True. \( \sum r^n < \infty \) since \( p < q \).
- (b) True. \( \pi_0 = 1 - r = \frac12 \).
- (c) False. \( \pi_1 = \frac14 \), so \( \mu_1 = 4 \). The value 2 is \( \mu_0 \).
- (d) False. With \( p = q \), detailed balance forces \( \pi_n = \pi_0 \) for all \( n \), which cannot sum to 1. The chain is null recurrent.
Quick Revision Table
| Idea | Fact |
|---|---|
| Stationary | \( \pi P = \pi \), \( \pi \ge 0 \), \( \sum \pi_j = 1 \) |
| Irreducible chain | \( \pi \) exists \( \iff \) positive recurrent; then unique, \( \pi_j = \frac{1}{\mu_j} \) |
| Finite chain | at least one \( \pi \); unique \( \iff \) one closed class; \( \pi = 0 \) on transient states |
| Two states | \( \pi = \left(\frac{b}{a + b}, \frac{a}{a + b}\right) \); second eigenvalue \( 1 - a - b \) |
| Doubly stochastic | uniform \( \pi \) |
| Graph walk | \( \pi_v = \frac{\deg v}{2\lvert E \rvert} \) |
| Birth–death | \( \pi_n = \pi_0\prod_{k=1}^{n}\frac{p_{k-1}}{q_k} \) |
| Convergence | irreducible + aperiodic + positive recurrent \( \Rightarrow p_{ij}^{(n)} \to \pi_j \) |
| Periodic | no limit; \( p_{jj}^{(nd)} \to d\pi_j \); Cesàro \( \to \pi_j \) |
| Transient / null | \( p_{ij}^{(n)} \to 0 \) |
| Reducible | \( p_{ij}^{(n)} \to h_i(C)\pi_j \) for \( j \) in aperiodic closed class \( C \) |
| Eigenvalue 1 | multiplicity = number of closed classes |
| Ehrenfest (\( N \) balls) | \( \pi = \text{Bin}(N, \frac12) \), period 2, \( \mu_0 = 2^N \) |
Key Takeaways
What’s Next
- Poisson and Birth-and-Death Processes: stationary distributions in continuous time, \( \pi Q = 0 \).
- Markov Chains and Classification of States: revisit classes and absorption if the limits above felt shaky.
- Markov Chains Quick Revision: every formula of the chapter on one page.
- Back to the chapter overview or the Mathematical Sciences overview.