Skip to content

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 read
  • Updated
On this page · 13 sections
  1. Prerequisites
  2. The Hook: The Walker Who Always Comes Home
  3. Markov Chains and Transition Matrices
  4. Communicating Classes
  5. Recurrence and Transience
  6. Absorption: First-Step Analysis
  7. Memory Tricks
  8. Don’t Confuse
  9. Common Mistakes
  10. Practice
  11. Quick Revision Table
  12. Key Takeaways
  13. What’s Next

Prerequisites

The Hook: The Walker Who Always Comes Home

Markov Chains and Transition Matrices

Markov chain

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

Accessibility and communication

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 --> S5

The 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).$$
Recurrent and transient states
State \( i \) is recurrent (persistent) if \( f_{ii} = 1 \), and transient if \( f_{ii} < 1 \). A recurrent state is positive recurrent if its mean recurrence time \( \mu_i = E[T_i \mid X_0 = i] \) is finite, and null recurrent if \( \mu_i = \infty \).

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}}.$$
Series criterion
$$i \text{ is recurrent} \iff \sum_{n=1}^{\infty} p_{ii}^{(n)} = \infty \iff P(X_n = i \text{ infinitely often} \mid X_0 = i) = 1.$$

$$i \text{ is transient} \iff \sum_{n=1}^{\infty} p_{ii}^{(n)} = \frac{f_{ii}}{1 - f_{ii}} < \infty \iff P(X_n = i \text{ infinitely often} \mid X_0 = i) = 0.$$

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.

FactHolds for
A recurrent class is closedevery chain
A class that is not closed is transientevery chain
A closed class is recurrentfinite classes only
A finite closed class is positive recurrentfinite classes
At least one state is recurrentfinite chains
No null recurrent statesfinite chains
An irreducible chain has all states of one typeevery 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

Period
The period of state \( i \) is \( d(i) = \gcd\{n \ge 1 : p_{ii}^{(n)} > 0\} \) (undefined, or taken as \( \infty \), if the set is empty). The state is aperiodic if \( d(i) = 1 \). The period is a class property.

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

ThisIs not thisThe difference
\( f_{ii} \) (return probability)\( p_{ii}^{(n)} \) (at \( i \) at time \( n \))\( f_{ii} = 1 \iff \sum_n p_{ii}^{(n)} = \infty \)
closed classrecurrent classequal for finite classes; biased walk on \( \mathbb{Z} \) is closed and transient
null recurrenttransientnull 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 \)
irreducibleaperiodic\( \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \) is irreducible with period 2
absorbing stateclosed classan 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

  1. What must every row of a transition matrix sum to?
  2. A state \( i \) has \( f_{ii} = \frac34 \). What is \( \sum_{n \ge 1} p_{ii}^{(n)} \)?
  3. State \( i \) of an irreducible chain has \( p_{ii} > 0 \). What is the period of the chain?
Answers
  1. 1. \( p_{ij} \ge 0 \) and \( \sum_j p_{ij} = 1 \).
  2. 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.)
  3. 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

IdeaFact
Markov propertyfuture depends on the past only through the present
Transition matrixstochastic: \( p_{ij} \ge 0 \), rows sum to 1
Chapman–Kolmogorov\( P^{(m+n)} = P^{(m)}P^{(n)} \); \( \mu^{(n)} = \mu^{(0)}P^n \)
Classesstrongly 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 chainsclosed \( \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 walkrecurrent for \( d \le 2 \), transient for \( d \ge 3 \)
Period\( \gcd\{n : p_{ii}^{(n)} > 0\} \); self-loop \( \Rightarrow 1 \)
Absorptionfirst-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