Markov Chains and Classification of States
CSIR NET statistics: discrete-time Markov chains on finite and countable spaces, Chapman–Kolmogorov, communicating classes, recurrence, period, absorption.
- 22 min
On this page · 13 sections
Prerequisites
- Counting, Probability and Number Properties: conditional probability and the multiplication rule, which is all the Markov property uses.
- Sequences, Series, limsup and liminf: recurrence is decided by whether a series \( \sum_n p_{ii}^{(n)} \) converges, and Stirling-type estimates decide that.
- Eigenvalues and the Cayley–Hamilton Theorem: \( n \)-step probabilities are entries of the matrix power \( P^n \).
The Hook: The Walker Who Always Comes Home
Markov Chains and Transition Matrices
A sequence of random variables \( (X_n)_{n \ge 0} \) taking values in a finite or countable set \( S \) (the state space) is a Markov chain if, for all \( n \ge 0 \) and all states \( i_0, \dots, i_{n-1}, i, j \),
$$P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i)$$whenever the conditioning event has positive probability. It is time-homogeneous if the right side does not depend on \( n \); we write it \( p_{ij} \). All chains in these notes are time-homogeneous.
The transition matrix \( P = (p_{ij})_{i, j \in S} \) is stochastic: \( p_{ij} \ge 0 \) and every row sums to 1. Rows are “from”, columns are “to”. If, in addition, every column sums to 1, \( P \) is doubly stochastic.
The law of the whole chain is fixed by \( P \) and the initial distribution \( \mu^{(0)}_i = P(X_0 = i) \):
$$P(X_0 = i_0, X_1 = i_1, \dots, X_n = i_n) = \mu^{(0)}_{i_0}\,p_{i_0i_1}\,p_{i_1i_2}\cdots p_{i_{n-1}i_n}.$$n-step transitions: Chapman–Kolmogorov
Let \( p_{ij}^{(n)} = P(X_{m+n} = j \mid X_m = i) \). Conditioning on the state at an intermediate time gives the Chapman–Kolmogorov equations
$$\boxed{p_{ij}^{(m+n)} = \sum_{k \in S} p_{ik}^{(m)}\,p_{kj}^{(n)}}, \qquad \text{i.e.} \quad P^{(m+n)} = P^{(m)}P^{(n)}.$$So the \( n \)-step matrix is the matrix power: \( P^{(n)} = P^n \), with \( P^0 = I \). Writing distributions as row vectors, the distribution at time \( n \) is
$$\mu^{(n)} = \mu^{(0)}P^n.$$Useful facts about stochastic matrices.
- \( P\mathbf{1} = \mathbf{1} \): 1 is always an eigenvalue (right eigenvector the all-ones column).
- Every eigenvalue satisfies \( \lvert \lambda \rvert \le 1 \) (the maximum row sum norm of \( P \) is 1).
- Products and powers of stochastic matrices are stochastic; so is any convex combination.
- A function of a Markov chain need not be Markov; a chain observed at times \( 0, k, 2k, \dots \) is Markov with matrix \( P^k \).
Communicating Classes
State \( j \) is accessible from \( i \) (\( i \to j \)) if \( p_{ij}^{(n)} > 0 \) for some \( n \ge 0 \). States \( i \) and \( j \) communicate (\( i \leftrightarrow j \)) if \( i \to j \) and \( j \to i \). Communication is an equivalence relation; its classes are the communicating classes.
- A class \( C \) is closed if \( i \in C \), \( i \to j \) imply \( j \in C \): the chain cannot leave it.
- A state \( i \) with \( p_{ii} = 1 \) is absorbing (a closed class on its own).
- The chain is irreducible if \( S \) is a single class.
How to find classes quickly. Draw the transition graph: an arrow \( i \to j \) whenever \( p_{ij} > 0 \). The numerical values do not matter, only which entries are positive. Classes are the strongly connected components; a class is closed if no arrow leaves it.
graph LR
S1((1)) <--> S2((2))
S3((3)) --> S2
S3 <--> S4((4))
S3 --> S3
S4 --> S5((5))
S5 --> S5The graph above is the chain in the worked example below. Classes: \( \{1, 2\} \) closed, \( \{3, 4\} \) not closed (arrows leave to 2 and 5), \( \{5\} \) closed (absorbing).
Recurrence and Transience
Let \( T_i = \min\{n \ge 1 : X_n = i\} \) be the first return time to \( i \) (\( T_i = \infty \) if the chain never returns), and
$$f_{ii} = P(T_i < \infty \mid X_0 = i), \qquad f_{ij}^{(n)} = P(T_j = n \mid X_0 = i).$$By the strong Markov property, each return starts the chain afresh, so the number of visits to \( i \) (counting time 0) is geometric:
$$P(\text{exactly } k \text{ visits} \mid X_0 = i) = f_{ii}^{\,k-1}(1 - f_{ii}), \qquad E[\text{visits}] = \sum_{n \ge 0} p_{ii}^{(n)} = \frac{1}{1 - f_{ii}}.$$For transient \( j \) and any \( i \), \( \sum_n p_{ij}^{(n)} < \infty \), hence \( p_{ij}^{(n)} \to 0 \).
The link between \( p^{(n)} \) and \( f^{(n)} \) is the first-passage decomposition \( p_{ij}^{(n)} = \sum_{k=1}^{n} f_{ij}^{(k)}\,p_{jj}^{(n-k)} \).
Class properties
Recurrence, transience, positive recurrence, null recurrence and the period are class properties: if \( i \leftrightarrow j \), both have the same type. So you classify a class by testing one convenient state.
| Fact | Holds for |
|---|---|
| A recurrent class is closed | every chain |
| A class that is not closed is transient | every chain |
| A closed class is recurrent | finite classes only |
| A finite closed class is positive recurrent | finite classes |
| At least one state is recurrent | finite chains |
| No null recurrent states | finite chains |
| An irreducible chain has all states of one type | every chain |
| If \( i \) is recurrent and \( i \to j \), then \( j \to i \), \( j \) is recurrent and \( f_{ji} = 1 \) | every chain |
Random walks: the countable case
The simple random walk on \( \mathbb{Z} \): \( p_{i,i+1} = p \), \( p_{i,i-1} = q = 1 - p \), \( 0 < p < 1 \). It is irreducible with period 2. Returns to 0 happen only at even times, and
$$p_{00}^{(2n)} = \binom{2n}{n}p^nq^n \sim \frac{(4pq)^n}{\sqrt{\pi n}} \quad \text{(Stirling)}.$$Since \( 4pq \le 1 \) with equality iff \( p = \frac{1}{2} \):
- \( p = \frac{1}{2} \): terms behave like \( \frac{1}{\sqrt{\pi n}} \), the series diverges, the walk is recurrent. It is null recurrent (it has no stationary distribution; see the next page).
- \( p \ne \frac{1}{2} \): geometric decay, the series converges, the walk is transient. Exactly, \( \sum_{n \ge 0}\binom{2n}{n}(pq)^n = \frac{1}{\sqrt{1 - 4pq}} = \frac{1}{\lvert p - q \rvert} \), so $$f_{00} = 1 - \lvert p - q \rvert.$$ For \( p = 0.6 \): \( f_{00} = 0.8 \), as in the hook.
Symmetric walk on \( \mathbb{Z}^d \) (each of the \( 2d \) neighbours with probability \( \frac{1}{2d} \)): \( p_{00}^{(2n)} \) decays like \( c_d\,n^{-d/2} \), so the walk is recurrent for \( d = 1, 2 \) and transient for \( d \ge 3 \) (Pólya’s theorem). In \( d = 1, 2 \) it is null recurrent.
Periodicity
Rules that settle most questions in seconds:
- A self-loop (\( p_{ii} > 0 \)) makes the whole class aperiodic.
- Read cycle lengths off the transition graph: \( d \) is the gcd of the lengths of all closed walks through \( i \). Cycles of lengths 2 and 3 through the same state give \( \gcd(2, 3) = 1 \).
- A walk that changes parity at each step (random walk on a bipartite graph, Ehrenfest urn, simple random walk on \( \mathbb{Z} \)) has period 2.
- A deterministic cycle \( 1 \to 2 \to \dots \to k \to 1 \) has period \( k \).
- If \( d(i) = d \), then \( p_{ii}^{(nd)} > 0 \) for all sufficiently large \( n \).
- An irreducible chain of period \( d \) splits into cyclic classes \( C_0, C_1, \dots, C_{d-1} \): from \( C_r \) the chain moves only to \( C_{r+1 \bmod d} \).
Absorption: First-Step Analysis
When a chain has transient states, two questions come up: where does it get absorbed, and how long does it take? Both are answered by conditioning on the first step.
For a set \( A \) of states, let \( h_i = P(\text{hit } A \mid X_0 = i) \) and \( k_i = E[\text{time to hit } A \mid X_0 = i] \). Then
$$h_i = 1 \ (i \in A), \qquad h_i = \sum_{j} p_{ij}h_j \ (i \notin A);$$$$k_i = 0 \ (i \in A), \qquad k_i = 1 + \sum_{j} p_{ij}k_j \ (i \notin A).$$On an infinite state space these systems can have several solutions; the hitting probabilities are the minimal non-negative solution.
Matrix form (finite absorbing chains). Order the states transient first, recurrent (absorbing) last:
$$P = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}, \qquad N = (I - Q)^{-1} \ (\text{fundamental matrix}).$$Then \( N_{ij} \) is the expected number of visits to transient \( j \) from transient \( i \), the absorption probabilities are \( B = NR \), and the expected times to absorption are \( t = N\mathbf{1} \). The inverse exists because \( Q^n \to 0 \).
Gambler’s ruin
A gambler with fortune \( i \) wins 1 with probability \( p \) and loses 1 with probability \( q = 1 - p \), stopping at 0 or \( N \). With \( r = \frac{q}{p} \):
$$P(\text{reach } N \text{ before } 0 \mid X_0 = i) = \begin{cases} \dfrac{1 - r^i}{1 - r^N}, & p \ne q, \\[2mm] \dfrac{i}{N}, & p = q = \frac12. \end{cases}$$For the fair game the expected duration is \( k_i = i(N - i) \). Letting \( N \to \infty \): against an infinitely rich adversary, ruin is certain if \( p \le \frac12 \) and has probability \( r^i \) if \( p > \frac12 \).
graph TD
A["Transition matrix P"] --> B["Draw graph of positive entries"]
B --> C["Find communicating classes"]
C --> D{"Class closed?"}
D -->|No| E["Transient"]
D -->|Yes| F{"Class finite?"}
F -->|Yes| G["Positive recurrent"]
F -->|No| H["Test a state: sum of p_ii^(n),
or a stationary distribution"]
C --> I["Period: gcd of cycle lengths
(self-loop gives 1)"]Memory Tricks
- Rows are “from”. \( p_{ij} \) is from \( i \) to \( j \), rows sum to 1, distributions multiply from the left: \( \mu P \).
- Closed and finite means recurrent. “Can’t get out, and nowhere to hide” (finitely many places), so the chain keeps coming back.
- Infinite sum, infinite returns. \( \sum p_{ii}^{(n)} = \infty \) is the same as “returns infinitely often” is the same as recurrent.
- One, two, home; three, free. The symmetric walk is recurrent in dimensions 1 and 2, transient from 3 on.
- One self-loop kills the period. \( p_{ii} > 0 \) makes the entire class aperiodic.
Don’t Confuse
| This | Is not this | The difference |
|---|---|---|
| \( f_{ii} \) (return probability) | \( p_{ii}^{(n)} \) (at \( i \) at time \( n \)) | \( f_{ii} = 1 \iff \sum_n p_{ii}^{(n)} = \infty \) |
| closed class | recurrent class | equal for finite classes; biased walk on \( \mathbb{Z} \) is closed and transient |
| null recurrent | transient | null recurrent returns with probability 1, but the mean return time is infinite |
| period \( d(i) \) | shortest return time | \( d \) is a gcd: returns at times 2 and 3 give \( d = 1 \) |
| irreducible | aperiodic | \( \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \) is irreducible with period 2 |
| absorbing state | closed class | an absorbing state is a closed class of size one |
| \( \mu P \) (row vector) | \( P\mu \) | the column version answers a different question (expected value of a function) |
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
- What must every row of a transition matrix sum to?
- A state \( i \) has \( f_{ii} = \frac34 \). What is \( \sum_{n \ge 1} p_{ii}^{(n)} \)?
- State \( i \) of an irreducible chain has \( p_{ii} > 0 \). What is the period of the chain?
Answers
- 1. \( p_{ij} \ge 0 \) and \( \sum_j p_{ij} = 1 \).
- 3. \( \sum_{n \ge 1} p_{ii}^{(n)} = \frac{f_{ii}}{1 - f_{ii}} = \frac{3/4}{1/4} = 3 \): the expected number of returns. (Counting time 0, the expected number of visits is 4.)
- 1. A self-loop gives a return at time 1, so the gcd is 1, and the period is a class property.
Level 2: Part B Style
Practice Q1. A Markov chain on \( \{1, 2, 3, 4, 5\} \) has the following positive transition probabilities (all others zero): \( 1 \to 2 \), \( 2 \to 1 \), \( 2 \to 3 \), \( 3 \to 3 \), \( 4 \to 5 \), \( 5 \to 4 \), \( 5 \to 1 \). The number of communicating classes and the number of closed classes are:
(a) 3 and 1 (b) 3 and 2 (c) 4 and 1 (d) 2 and 1
Answer: (a)
Classes: \( \{1, 2\} \) (since \( 1 \leftrightarrow 2 \)), \( \{3\} \), \( \{4, 5\} \). That is 3 classes. \( \{3\} \) is closed (only \( 3 \to 3 \)); \( \{1, 2\} \) leaks to 3; \( \{4, 5\} \) leaks to 1. Exactly one closed class, so 3 is the only recurrent state.
Practice Q2. A gambler starts with 2 units and plays until she has 4 units or is ruined. Each play she wins one unit with probability \( \frac23 \) and loses one with probability \( \frac13 \). The probability that she reaches 4 units is:
(a) \( \frac23 \) (b) \( \frac34 \) (c) \( \frac45 \) (d) \( \frac{8}{9} \)
Answer: (c)
\( r = \frac{q}{p} = \frac12 \). \( P = \frac{1 - r^2}{1 - r^4} = \frac{3/4}{15/16} = \frac45 \). (Shortcut: \( \frac{1 - r^2}{1 - r^4} = \frac{1}{1 + r^2} \).)
Practice Q3. A chain on \( \{1, 2, 3\} \) has \( p_{12} = 1 \), \( p_{21} = p_{23} = \frac12 \), \( p_{31} = 1 \). The period of state 1 is:
(a) 1 (b) 2 (c) 3 (d) 6
Answer: (a)
Returns to 1: \( 1 \to 2 \to 1 \) (length 2) and \( 1 \to 2 \to 3 \to 1 \) (length 3). \( \gcd(2, 3) = 1 \). Option (b) is the length of the shortest return, which is not the period.
Practice Q4. For the simple random walk on \( \mathbb{Z} \) with \( p_{i,i+1} = 0.7 \), \( p_{i,i-1} = 0.3 \), the probability that the walk started at 0 ever returns to 0 is:
(a) 0.3 (b) 0.4 (c) 0.6 (d) 1
Answer: (c)
\( f_{00} = 1 - \lvert p - q \rvert = 1 - 0.4 = 0.6 \). Check through the series: \( \sum_{n \ge 0}p_{00}^{(n)} = \frac{1}{\lvert p - q \rvert} = 2.5 = \frac{1}{1 - f_{00}} \), so \( f_{00} = 0.6 \). (Intuition: if the first step is to \( -1 \), probability 0.3, the upward drift brings it back for sure; if it is to \( +1 \), probability 0.7, it returns only with probability \( \frac{q}{p} = \frac37 \). Total \( 0.3 + 0.7 \cdot \frac37 = 0.6 \).)
Level 3: Part C Style
Practice Q5. Let \( (X_n) \) be a Markov chain on a finite state space \( S \). Which of the following statements are true?
(a) At least one state is recurrent. (b) Some state may be null recurrent. (c) Every closed communicating class is recurrent. (d) If the chain is irreducible, all its states are aperiodic.
Answer: (a) and (c)
- (a) True. If every state were transient, each would be visited finitely often almost surely; with finitely many states the chain would have nowhere to be after some time, which is impossible.
- (b) False. In a finite closed class the expected return time is finite, so recurrent states of finite chains are positive recurrent.
- (c) True. A finite closed class is itself a finite irreducible chain, so by (a) it has a recurrent state, and recurrence is a class property.
- (d) False. \( \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \) is irreducible with period 2.
Practice Q6. For the five-state chain of the worked example above (states \( 1, \dots, 5 \), \( \{1, 2\} \) closed, \( \{3, 4\} \) transient, 5 absorbing), which statements are true?
(a) Starting from 4, the chain is absorbed at 5 with probability \( \frac34 \). (b) Starting from 3, the expected number of visits to 4 before absorption is 1. (c) \( p_{33}^{(n)} \to 0 \) as \( n \to \infty \). (d) Starting from 3, the expected time to leave \( \{3, 4\} \) is 2.
Answer: (a), (b) and (c)
- (a) True. \( h_4 = \frac14 \) for absorption in \( \{1, 2\} \), so absorption at 5 has probability \( 1 - \frac14 = \frac34 \).
- (b) True. \( N = (I - Q)^{-1} = \begin{pmatrix} 2 & 1 \\ 1 & \frac32 \end{pmatrix} \); \( N_{34} = 1 \).
- (c) True. State 3 is transient, so \( \sum_n p_{33}^{(n)} < \infty \) and the terms tend to 0.
- (d) False. The expected time is the row sum \( N_{33} + N_{34} = 3 \), not 2. (Option (d) is \( N_{33} \) alone: the expected number of visits to 3, counting time 0.)
Practice Q7. Consider the symmetric simple random walk on \( \mathbb{Z}^d \), moving to each of the \( 2d \) nearest neighbours with probability \( \frac{1}{2d} \). Which statements are true?
(a) For every \( d \), the walk is irreducible with period 2. (b) For \( d = 2 \), the origin is recurrent. (c) For \( d = 3 \), \( \sum_{n} p_{00}^{(n)} < \infty \). (d) For \( d = 1 \), the expected return time to the origin is finite.
Answer: (a), (b) and (c)
- (a) True. Every state reaches every other; each step changes the sum of the coordinates by \( \pm 1 \), so returns take an even number of steps, and \( 2 \) steps (out and back) suffice.
- (b) True. \( p_{00}^{(2n)} \sim \frac{c}{n} \) in \( d = 2 \); the harmonic series diverges.
- (c) True. \( p_{00}^{(2n)} \sim cn^{-3/2} \) in \( d = 3 \): a convergent series, so the origin is transient.
- (d) False. In \( d = 1 \) the walk is null recurrent: it returns with probability 1, but \( E[T_0] = \infty \). (If it were positive recurrent, an irreducible chain would have a stationary distribution; a stationary distribution on \( \mathbb{Z} \) for the symmetric walk would have to be constant, which cannot sum to 1.)
Quick Revision Table
| Idea | Fact |
|---|---|
| Markov property | future depends on the past only through the present |
| Transition matrix | stochastic: \( p_{ij} \ge 0 \), rows sum to 1 |
| Chapman–Kolmogorov | \( P^{(m+n)} = P^{(m)}P^{(n)} \); \( \mu^{(n)} = \mu^{(0)}P^n \) |
| Classes | strongly connected components of the graph of positive entries |
| Recurrent | \( f_{ii} = 1 \iff \sum p_{ii}^{(n)} = \infty \) |
| Transient | \( \sum_{n \ge 1} p_{ii}^{(n)} = \frac{f_{ii}}{1 - f_{ii}} \) |
| Finite chains | closed \( \iff \) recurrent (positive); at least one recurrent state; no null states |
| Random walk on \( \mathbb{Z} \) | recurrent iff \( p = \frac12 \) (null); \( f_{00} = 1 - \lvert p - q \rvert \) |
| \( \mathbb{Z}^d \) symmetric walk | recurrent for \( d \le 2 \), transient for \( d \ge 3 \) |
| Period | \( \gcd\{n : p_{ii}^{(n)} > 0\} \); self-loop \( \Rightarrow 1 \) |
| Absorption | first-step analysis; \( N = (I - Q)^{-1} \), \( B = NR \), \( t = N\mathbf{1} \) |
| Gambler’s ruin | \( \frac{1 - r^i}{1 - r^N} \), \( r = \frac{q}{p} \); fair: \( \frac{i}{N} \), duration \( i(N - i) \) |
Key Takeaways
What’s Next
- n-Step Transition Limits and Stationary Distributions: what \( P^n \) converges to, and when.
- Poisson and Birth-and-Death Processes: the same ideas in continuous time.
- Markov Chains Quick Revision: the whole chapter on one page.
- Back to the chapter overview or the Mathematical Sciences overview.