Markov Chain State Classification

Author

John Robin Inston

Published

September 25, 2026

Throughout, \(\{X_{n}\}\) is a homogeneous Markov chain with countable state space \(S\), \(p_{i,j}(n)=\mathbb{P}(X_{n}=j|X_{0}=i)\), and \(T_{j}\), \(f_{i,j}\), \(\mu_{j}\) are the first hitting time, hitting probability and mean recurrence time of Markov Chain Passage & Recurrence Times.

1 Communication and Irreducibility

State \(i\) communicates with state \(j\) (or \(j\) is accessible from \(i\)), denoted \(i \to j\) if \(p_{i,j}(n)>0\) for some \(n\geq 0\) that is, there is positive probability for the chain to visit \(j\) when starting from \(i\).

  • If \(i \neq j\) this is equivalent to \(f_{i,j}=\mathbb{P}(T_{j}<\infty|X_{0}=i)>0\).
  • If \(i = j\), then \(p_{i,i}(0)=1\) so that \(i \to i\) but it is possible for \(f_{i,i}=\sum_{n=1}^\infty f_{i,i}(n)=0\), that is, the chain might leave \(i\) immediately and never return to it.

States \(i\) and \(j\) inter-communicate if \(i \to j\) and \(j \to i\), denoted \(i\leftrightarrow j\) and we have the following results:

  1. States \(i\) and \(j\) have the same period;
  2. State \(i\) is transient iff \(j\) is transient; and
  3. State \(i\) is null persistent iff \(j\) is.

A set of states \(C\) is irreducible if for all \(i,j\in C\), \(i\leftrightarrow j\), that is all states within \(C\) inter-communicate.

A set of states \(C\) is closed if for all \(i \in C\), \(p_{i,j}=0\) for all \(j\not\in C\), that is, the chain never leaves \(C\) once it has entered. Note that clearly the set consisting of one absorbing state is closed.

2 Persistence

A state \(j\) is persistent if the probability that the process will return to \(j\) given that it started at \(j\) eventually is 1. This is equivalent to writing \[ \mathbb{P}(X_{n}=j~\text{for some}~n\geq 1|X_{0}=j)=1. \] Notice too that this is equivalent to each of the following:

  1. The probability that the first hitting time of state \(j\) is finite given the process started at \(j\) is 1 i.e. \(\mathbb{P}(T_{i}<\infty|X_{0}=i)=1\) or equivalently \(\mathbb{P}(T_{i}=\infty|X_{0}=i)=0\);
  2. The sum of the \(n\) step transition probabilities from \(j\) to \(j\) for all \(n\in \mathbb{N}\) is infinite i.e. \(\sum_{n}p_{j,j}(n)=\infty\);
  3. The probability that the chain ever visits \(j\) having started at \(j\) is 1 i.e. \(f_{j,j}=1\).
  4. The expected number of visits \(N_{j}\) to state \(j\) is infinite i.e. \(\mathbb{E}[N_{j}|X_{0}=i]=\infty\).

A state \(j\) is null-persistent if it is persistent but the mean recurrence time is still infinite i.e. \(\mu_{i}=\infty\). Otherwise the state is known as non-null or positive persistent.

For example we consider a random walk whereby any point in the state space is null-persistent since the random walk can always return but may take infinitely long to do so.

3 Transience

Alternatively, if a state \(j\) is not persistent it must be transient, that is, the probability that the process will return to \(j\) given that it started at \(j\) eventually is 0 i.e. the processes structure prevents it from returning. This is equivalent to writing \[ \mathbb{P}(X_{n}=i~\text{for some}~n\geq 1|X_{0}=i)<1 \] As above, notice that this is equivalent to each of the following:

  1. \(\mathbb{P}(T_{i}=\infty|X_{0}=i)>0\);
  2. \(\sum_{n}p_{j,j}(n)<\infty\)
  3. \(f_{j,j}<1\)
  4. \(\mathbb{E}[N_{j}|X_{0}=i]<\infty\)

Note that if a state \(j\) is transient we must have that \(p_{i,j}(n) \to 0\) as \(n \to \infty\) for all \(i\) since \(\sum_{n}p_{{i,j}}(n)<\infty\). Intuitively, this is stating that since \(j\) is transient, the probability that the chain visits \(j\) as time \(n\) goes to infinity approaches 0.

4 Periodicity & Ergodicity

The period of a state \(j\) is the greatest common divider of all \(n\) for which \(p_{{i,i}}(n)>0\) i.e. \[ d(i)=gcd\{n:p_{i,i}(n)>0\}. \] If \(d(i)=1\) then the state \(j\) is aperiodic and otherwise, the state is said to be periodic.

A state \(j\) is ergodic if it is positive persistent and aperiodic i.e. \(\mu_{i,i}<\infty\) and \(d(i)=1\).

A state \(j\) is absorbing if \(p_{j,j}=1\), that is the probability of leaving state \(j\) once the process has entered is 0.

5 Example: communication classes

Consider the chain with the transition diagram below.

Example transition probability diagram.

Let \(S_{1}=\{5\}\), \(S_{2}=\{1,2,3,4\}\) and \(S_{3}=\{6,7\}\). The chain is reducible since \(2\to5\) and \(3\to6\) are one-way journeys. State \(5\) is absorbing since the chain can never leave it. States \(1,2,3,4\) are transient since the chain eventually leaves them and never returns, and states \(6,7\) are persistent since the chain always revisits them. So \(S_{1}\) is a closed persistent (absorbing) class, \(S_{2}\) is a transient class and \(S_{3}\) is a closed persistent class. The long-run behaviour is discussed in Markov Chain Stationary Distributions and Markov Chain Equilibrium Convergence.

Back to top