11.2.4 Classification of States
 $$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$.
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.
 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*}

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*}
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.
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:
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 $1f_{ii}$.
 If $i$ is a recurrent state, then $$P(V=\inftyX_0=i)=1.$$
 If $i$ is a transient state, then $$V  X_0=i \; \sim \; Geometric(1f_{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$. $$If $d(i)>1$, we say that state $i$ is periodic.
 $$If $d(i)=1$, we say that state $i$ is aperiodic.
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 coprime if their greatest common divisor (gcd) is $1$, i.e., $\textrm{gcd}(l,m)=1$. Now, suppose that we can find two coprime 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 coprime to every integer, any state with a selftransition is aperiodic.
 If there is a selftransition in the chain ($p_{ii}>0$ for some $i$), then the chain is aperiodic.
 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.
 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., \begin{align*} p^{(n)}_{ij}>0, \; \textrm{ for all }i,j \in S. \end{align*}
Example
Consider the Markov chain in Example 11.6.
 Is $\textrm{Class 1}=\{\textrm{state } 1, \textrm{state } 2\}$ aperiodic?
 Is $\textrm{Class 2}=\{\textrm{state }3,\textrm{state }4\}$ aperiodic?
 Is $\textrm{Class 4}=\{\textrm{state }6,\textrm{state }7,\textrm{state }8\}$ aperiodic?
 Solution

 $\textrm{Class 1}=\{\textrm{state } 1, \textrm{state } 2\}$ is aperiodic since it has a selftransition, $p_{22}>0$.
 $\textrm{Class 2}=\{\textrm{state }3,\textrm{state }4\}$ is periodic with period $2$.
 $\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 ($676$) and in three steps ($6786$). Since $\textrm{gcd}(2,3)=1$, we conclude state $6$ and its class are aperiodic.
