←
→

11.2.4 Classification of States

To better understand Markov chains, we need to introduce some definitions. The first definition concerns the accessibility of states from each other: If it is possible to go from state $i$ to state $j$, we say that state $j$ is accessible from state $i$. In particular, we can provide the following definitions.
We say that state $j$ is accessible from state $i$, written as $i \rightarrow j$, if $p^{(n)}_{ij}>0$ for some $n$. We assume every state is accessible from itself since $p^{(0)}_{ii}=1$.
Two states $i$ and $j$ are said to communicate, written as $i \leftrightarrow j$, if they are accessible from each other. In other words, \begin{align*} i \leftrightarrow j \; \textrm{ means } \; i \rightarrow j \textrm{ and } j \rightarrow i. \end{align*}
Communication is an equivalence relation. That means that
$-$every state communicates with itself, $i\leftrightarrow i$;
$-$if $i \leftrightarrow j$, then $j \leftrightarrow i$;
$-$if $i \leftrightarrow j$ and $j \leftrightarrow k$, then $i \leftrightarrow k$.
Therefore, the states of a Markov chain can be partitioned into communicating classes such that only members of the same class communicate with each other. That is, two states $i$ and $j$ belong to the same class if and only if $i \leftrightarrow j$.

Example
Consider the Markov chain shown in Figure 11.9. It is assumed that when there is an arrow from state $i$ to state $j$, then $p_{ij}>0$. Find the equivalence classes for this Markov chain.
MC-diagram-3
Figure 11.9 - A state transition diagram.
  • Solution
    • There are four communicating classes in this Markov chain. Looking at Figure 11.10, we notice that states $1$ and $2$ communicate with each other, but they do not communicate with any other nodes in the graph. Similarly, nodes $3$ and $4$ communicate with each other, but they do not communicate with any other nodes in the graph. State $5$ does not communicate with any other states, so it by itself is a class. Finally, states $6$, $7$, and $8$ construct another class. Thus, here are the classes: \begin{align*} &\textrm{Class 1}=\{\textrm{state } 1, \textrm{state } 2\},\\ &\textrm{Class 2}=\{\textrm{state }3,\textrm{state }4\},\\ &\textrm{Class 3}=\{\textrm{state } 5\},\\ &\textrm{Class 4}=\{\textrm{state }6,\textrm{state }7,\textrm{state }8\}. \end{align*}
      MC-diagram-4
      Figure 11.10 - Equivalence classes.

A Markov chain is said to be irreducible if it has only one communicating class. As we will see shortly, irreducibility is a desirable property in the sense that it can simplify analysis of the limiting behavior.
A Markov chain is said to be irreducible if all states communicate with each other.

Looking at Figure 11.10, we notice that there are two kinds of classes. In particular, if at any time the Markov chain enters Class $4$, it will always stay in that class. On the other hand, for other classes this is not true. For example, if $X_0=1$, then the Markov chain might stay in Class $1$ for a while, but at some point, it will leave that class and it will never return to that class again. The states in Class $4$ are called recurrent states, while the other states in this chain are called transient.

In general, a state is said to be recurrent if, any time that we leave that state, we will return to that state in the future with probability one. On the other hand, if the probability of returning is less than one, the state is called transient. Here, we provide a formal definition:

For any state $i$, we define \begin{align*} f_{ii}=P(X_n=i, \textrm{ for some }n \geq 1 | X_0=i). \end{align*} State $i$ is recurrent if $f_{ii}=1$, and it is transient if $f_{ii}<1$.

It is relatively easy to show that if two states are in the same class, either both of them are recurrent, or both of them are transient. Thus, we can extend the above definitions to classes. A class is said to be recurrent if the states in that class are recurrent. If, on the other hand, the states are transient, the class is called transient. In general, a Markov chain might consist of several transient classes as well as several recurrent classes.

Consider a Markov chain and assume $X_0=i$. If $i$ is a recurrent state, then the chain will return to state $i$ any time it leaves that state. Therefore, the chain will visit state $i$ an infinite number of times. On the other hand, if $i$ is a transient state, the chain will return to state $i$ with probability $f_{ii}<1$. Thus, in that case, the total number of visits to state $i$ will be a Geometric random variable with parameter $1-f_{ii}$.

Consider a discrete-time Markov chain. Let $V$ be the total number of visits to state $i$.
  1. If $i$ is a recurrent state, then $$P(V=\infty|X_0=i)=1.$$
  2. If $i$ is a transient state, then $$V | X_0=i \; \sim \; Geometric(1-f_{ii}).$$

Example
Show that in a finite Markov chain, there is at least one recurrent class.
  • Solution
    • Consider a finite Markov chain with $r$ states, $S=\{1,2,\cdots, r\}$. Suppose that all states are transient. Then, starting from time $0$, the chain might visit state $1$ several times, but at some point the chain will leave state $1$ and will never return to it. That is, there exists an integer $M_1 >0$ such that $X_n \neq 1$, for all $n \geq M_1$. Similarly, there exists an integer $M_2 >0$ such that $X_n \neq 2$, for all $n \geq M_2$, and so on. Now, if you choose \begin{align*} n \geq \max \{M_1, M_2, \cdots, M_r \}, \end{align*} then $X_n$ cannot be equal to any of the states $1,2,\cdots, r$. This is a contradiction, so we conclude that there must be at least one recurrent state, which means that there must be at least one recurrent class.

Periodicity:

Consider the Markov chain shown in Figure 11.11. There is a periodic pattern in this chain. Starting from state $0$, we only return to $0$ at times $n=3, 6, \cdots$. In other words, $p^{(n)}_{00}=0$, if $n$ is not divisible by $3$. Such a state is called a periodic state with period $d(0)=3$.
MC-diagram-periodic
Figure 11.11 - A state transition diagram.
The period of a state $i$ is the largest integer $d$ satisfying the following property: $p^{(n)}_{ii}=0$, whenever $n$ is not divisible by $d$. The period of $i$ is shown by $d(i)$. If $p^{(n)}_{ii}=0$, for all $n>0$, then we let $d(i)=\infty$.
$-$If $d(i)>1$, we say that state $i$ is periodic.
$-$If $d(i)=1$, we say that state $i$ is aperiodic.
You can show that all states in the same communicating class have the same period. A class is said to be periodic if its states are periodic. Similarly, a class is said to be aperiodic if its states are aperiodic. Finally, a Markov chain is said to be aperiodic if all of its states are aperiodic.
If $i \leftrightarrow j$, then $d(i)=d(j)$.

Why is periodicity important? As we will see shortly, it plays a role when we discuss limiting distributions. It turns out that in a typical problem, we are given an irreducible Markov chain, and we need to check if it is aperiodic.

How do we check that a Markov chain is aperiodic? Here is a useful method. Remember that two numbers $m$ and $l$ are said to be co-prime if their greatest common divisor (gcd) is $1$, i.e., $\textrm{gcd}(l,m)=1$. Now, suppose that we can find two co-prime numbers $l$ and $m$ such that $p^{(l)}_{ii}>0$ and $p^{(m)}_{ii}>0$. That is, we can go from state $i$ to itself in $l$ steps, and also in $m$ steps. Then, we can conclude state $i$ is aperiodic. If we have an irreducible Markov chain, this means that the chain is aperiodic. Since the number $1$ is co-prime to every integer, any state with a self-transition is aperiodic.

Consider a finite irreducible Markov chain $X_n$:
  1. If there is a self-transition in the chain ($p_{ii}>0$ for some $i$), then the chain is aperiodic.
  2. Suppose that you can go from state $i$ to state $i$ in $l$ steps, i.e., $p^{(l)}_{ii}>0$. Also suppose that $p^{(m)}_{ii}>0$. If $\textrm{gcd}(l,m)=1$, then state $i$ is aperiodic.
  3. The chain is aperiodic if and only if there exists a positive integer $n$ such that all elements of the matrix $P^n$ are strictly positive, i.e.,
    4. \begin{align*} p^{(n)}_{ij}>0, \; \textrm{ for all }i,j \in S. \end{align*}

Example
Consider the Markov chain in Example 11.6.
  1. Is $\textrm{Class 1}=\{\textrm{state } 1, \textrm{state } 2\}$ aperiodic?
  2. Is $\textrm{Class 2}=\{\textrm{state }3,\textrm{state }4\}$ aperiodic?
  3. Is $\textrm{Class 4}=\{\textrm{state }6,\textrm{state }7,\textrm{state }8\}$ aperiodic?
  • Solution
      1. $\textrm{Class 1}=\{\textrm{state } 1, \textrm{state } 2\}$ is aperiodic since it has a self-transition, $p_{22}>0$.
      2. $\textrm{Class 2}=\{\textrm{state }3,\textrm{state }4\}$ is periodic with period $2$.
      3. $\textrm{Class 4}=\{\textrm{state }6,\textrm{state }7,\textrm{state }8\}$ is aperiodic. For example, note that we can go from state $6$ to state $6$ in two steps ($6-7-6$) and in three steps ($6-7-8-6$). Since $\textrm{gcd}(2,3)=1$, we conclude state $6$ and its class are aperiodic.

←
→

The print version of the book is available on Amazon.

Book Cover


Practical uncertainty: Useful Ideas in Decision-Making, Risk, Randomness, & AI

ractical Uncertaintly Cover