Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 36 ยท Markov Chains

Classification of States: Communicating Classes, Recurrent and Transient

Classify Markov chain states: accessibility, communicating classes, closed and absorbing classes, recurrent versus transient, with a Python class finder.

Some Markov chains wander forever among all their states. Others get stuck, or leave a region and never return. To predict long-run behavior you first need to know the chain's structure: which states connect to which, and which states the chain keeps coming back to. This lesson gives the vocabulary and a program to find it.

Accessibility and communication

State j is accessible from i (write i โ†’ j) if the chain starting at i can reach j in some number of steps with positive probability: p_ij^(n) > 0 for some n >= 0. States i and j communicate (i โ†” j) if each is accessible from the other.

Communication is an equivalence relation: it is reflexive, symmetric and transitive. So it splits the state space into communicating classes. A chain with only one class is called irreducible.

A class is closed if no state outside it is accessible from inside it: once in, the chain never leaves. A closed class of one state is an absorbing state: p_ii = 1.

A worked example

Take five states with this transition matrix:

from \ to 0 1 2 3 4
0 0.5 0.5 0 0 0
1 0.4 0.2 0.4 0 0
2 0 0 0.3 0.7 0
3 0 0 0.6 0.4 0
4 0 0 0 0 1
flowchart LR
    s0((0)) -->|"0.5"| s1((1))
    s1 -->|"0.4"| s0
    s1 -->|"0.4"| s2((2))
    s2 -->|"0.7"| s3((3))
    s3 -->|"0.6"| s2
    s4((4))

Self-loops omitted. States 0 and 1 communicate and leak into {2, 3}; state 4 is on its own.

Reading the picture: 0 โ†” 1, 2 โ†” 3, and 4 stands alone. The communicating classes are {0, 1}, {2, 3} and . From {0, 1} you can leave (via 1 โ†’ 2) and never come back, so that class is not closed. The classes {2, 3} and are closed, and 4 is absorbing.

Finding classes by program

Compute reachability from the pattern of positive entries, then pair up mutual reachability.

Python Find the communicating classes automatically

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Recurrent and transient states

Start the chain at i. Let f_i be the probability that it ever returns to i.

  • State i is recurrent if f_i = 1: the chain returns for sure, and therefore returns again and again, infinitely often.
  • State i is transient if f_i < 1: with positive probability the chain never returns, so it visits i only finitely many times.

Facts to remember:

  1. Recurrence and transience are class properties: all states in a communicating class are of the same type.
  2. In a finite chain, a class is recurrent if and only if it is closed. A non-closed class is transient.
  3. At least one state of a finite chain is recurrent, since the chain has to end up somewhere.
  4. In an infinite chain, a closed class can still be transient (the symmetric random walk on the integers is recurrent in 1D and 2D, but the walk in 3D is transient; the biased walk on the integers is transient).

For our example: {0, 1} is transient; {2, 3} and are recurrent.

How many visits to a transient state?

If f_i < 1, then the number of visits to i (counting time 0), starting from i, is geometric with mean 1/(1 - f_i). For our chain, let us test by simulation. The expected number of visits to state 0 when starting there can be computed with the fundamental matrix; the value is 4 (you will derive it in the next lesson).

Python A transient state is visited only finitely often

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A recurrent state can have a very long return time and still be recurrent. Recurrence is about returning with probability 1, not about returning soon. The mean return time has its own classification: positive recurrent (finite mean) and null recurrent (infinite mean). In finite chains every recurrent state is positive recurrent.

Why classification matters

Structure What happens in the long run
Irreducible finite chain all states recurrent; the chain keeps visiting everything
Transient class leaking into a closed class the chain eventually enters a closed class and stays
Several closed classes the chain's fate depends on which one it enters
Absorbing state the chain stops forever once it arrives

The next lesson studies chains that end in absorbing states, and later chapters study the long-run behavior of irreducible chains.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A communicating class is closed if...

    Closed means that once the chain enters the class it can never leave.
  2. 2. In a finite Markov chain, a class that is NOT closed is...

    With positive probability the chain leaves the class and never comes back, so its states are transient.
  3. 3. A state with p_ii = 1 is called...

    The chain stays there forever once it arrives.
  4. 4. An irreducible chain has how many communicating classes?

    Irreducible means every state communicates with every other state, so there is a single class.

Summary

  • i โ†’ j means j is reachable from i; i โ†” j means both directions; classes are the groups of mutually reachable states.
  • A class is closed if the chain cannot leave it; a closed class of one state is absorbing.
  • Recurrent: return with probability 1. Transient: positive probability of never returning.
  • In a finite chain, closed classes are recurrent and non-closed classes are transient.

Next: Absorbing Chains and Hitting Probabilities