---

Here, we would like to discuss long-term behavior of Markov chains. In particular, we would like to know the fraction of times that the Markov chain spends in each state as $n$ becomes large. More specifically, we would like to study the distributions \begin{equation} \pi^{(n)} = \begin{bmatrix} P(X_n=0) & P(X_n=1) & \cdots & \end{bmatrix} \end{equation} as $n \rightarrow \infty$. To better understand the subject, we will first look at an example and then provide a general analysis.

---

Example
Consider a Markov chain with two possible states, $S=\{0,1\}$. In particular, suppose that the transition matrix is given by \begin{equation} P = \begin{bmatrix} 1-a & a \\[5pt] b & 1-b \end{bmatrix}, \end{equation} where $a$ and $b$ are two real numbers in the interval $[0,1]$ such that $0 \lt a+b \lt 2$. Suppose that the system is in state $0$ at time $n=0$ with probability $\alpha$, i.e., \begin{align*} \pi^{(0)} = \begin{bmatrix} P(X_0=0) & P(X_0=1) \end{bmatrix} = \begin{bmatrix} \alpha & 1-\alpha \end{bmatrix}, \end{align*} where $\alpha \in [0,1]$.

1. Using induction (or any other method), show that \begin{align*} P^n=\frac{1}{a+b} \begin{bmatrix} b & a \\[5pt] b & a \end{bmatrix}+\frac{(1-a-b)^n}{a+b} \begin{bmatrix} a & -a \\[5pt] -b & b \end{bmatrix}. \end{align*}
2. Show that \begin{align*} \lim_{n \rightarrow \infty} P^n=\frac{1}{a+b} \begin{bmatrix} b & a \\[5pt] b & a \end{bmatrix}. \end{align*}
3. Show that \begin{align*} \lim_{n \rightarrow \infty} \pi^{(n)}=\begin{bmatrix} \frac{b}{a+b} & \frac{a}{a+b} \end{bmatrix}. \end{align*}

---

In the above example, the vector \begin{align*} \lim_{n \rightarrow \infty} \pi^{(n)}= \begin{bmatrix} \frac{b}{a+b} & \frac{a}{a+b} \end{bmatrix} \end{align*} is called the limiting distribution of the Markov chain. Note that the limiting distribution does not depend on the initial probabilities $\alpha$ and $1-\alpha$. In other words, the initial state ($X_0$) does not matter as $n $ becomes large. Thus, for $i=1, 2$, we can write \begin{align*} &\lim_{n \rightarrow \infty} P(X_n=0 |X_0=i)=\frac{b}{a+b},\\ &\lim_{n \rightarrow \infty} P(X_n=1 |X_0=i)=\frac{a}{a+b}. \end{align*} Remember that we show $P(X_n=j |X_0=i)$ by $P^{(n)}_{ij}$, which is the entry in the $i$th row and $j$th column of $P^n$. By the above definition, when a limiting distribution exists, it does not depend on the initial state ($X_0=i$), so we can write \begin{align*} \pi_j=\lim_{n \rightarrow \infty} P(X_n=j), \; \textrm{for all $j \in S$.} \end{align*} So far we have shown that the Markov chain in Example 11.12 has the following limiting distribution: \begin{align*} \pi=\begin{bmatrix} \pi_0 & \pi_1 \end{bmatrix}= \begin{bmatrix} \frac{b}{a+b} & \frac{a}{a+b} \end{bmatrix}. \end{align*} Let's now look at mean return times for this Markov chain.

---

Example
Consider a Markov chain in Example 11.12: a Markov chain with two possible states, $S=\{0,1\}$, and the transition matrix \begin{equation} P = \begin{bmatrix} 1-a & a \\[5pt] b & 1-b \end{bmatrix}, \end{equation} where $a$ and $b$ are two real numbers in the interval $[0,1]$ such that $0 \lt a+b \lt 2$. Find the mean return times, $r_0$ and $r_1$, for this Markov chain.

---

The two-state Markov chain discussed above is a "nice" one in the sense that it has a well-defined limiting behavior that does not depend on the initial probability distribution (PMF of $X_0$). However, not all Markov chains are like that. For example, consider the same Markov chain; however, choose $a=b=1$. In this case, the chain has a periodic behavior, i.e., \begin{align*} X_{n+2}=X_{n}, \quad \textrm{ for all }n. \end{align*} In particular, \begin{align} X_n = \left\{ \begin{array}{l l} X_0 & \quad \textrm{if $n$ is even} \\ & \quad \\ X_1 & \quad \text{if $n$ is odd} \end{array} \right. \end{align} In this case, the distribution of $X_n$ does not converge to a single PMF. Also, the distribution of $X_n$ depends on the initial distribution. As another example, if we choose $a=b=0$, the chain will consist of two disconnected nodes. In this case, \begin{align*} X_{n}=X_{0}, \quad \textrm{ for all }n. \end{align*} Here again, the PMF of $X_n$ depends on the initial distribution. Now, the question that arises here is: when does a Markov chain have a limiting distribution (that does not depend on the initial PMF)? We will next discuss this question. We will first consider finite Markov chains and then discuss infinite Markov chains.

Finite Markov Chains:

Here, we consider Markov chains with a finite number of states. In general, a finite Markov chain can consist of several transient as well as recurrent states. As $n$ becomes large the chain will enter a recurrent class and it will stay there forever. Therefore, when studying long-run behaviors we focus only on the recurrent classes.

If a finite Markov chain has more than one recurrent class, then the chain will get absorbed in one of the recurrent classes. Thus, the first question is: in which recurrent class does the chain get absorbed? We have already seen how to address this when we discussed absorption probabilities (see Section 11.2.5, and Problem 2 of in Section 11.2.7).

Thus, we can limit our attention to the case where our Markov chain consists of one recurrent class. In other words, we have an irreducible Markov chain. Note that as we showed in Example 11.7, in any finite Markov chain, there is at least one recurrent class. Therefore, in finite irreducible chains, all states are recurrent.

It turns out that in this case the Markov chain has a well-defined limiting behavior if it is aperiodic (states have period $1$). How do we find the limiting distribution? The trick is to find a stationary distribution. Here is the idea: If $\pi=[\pi_1, \pi_2, \cdots ]$ is a limiting distribution for a Markov chain, then we have \begin{align*} \pi&=\lim_{n \rightarrow \infty} \pi^{(n)}\\ &=\lim_{n \rightarrow \infty} \big[\pi^{(0)} P^n\big]. \end{align*} Similarly, we can write \begin{align*} \pi&=\lim_{n \rightarrow \infty} \pi^{(n+1)}\\ &=\lim_{n \rightarrow \infty} \big[\pi^{(0)} P^{n+1}\big]\\ &=\lim_{n \rightarrow \infty} \big[\pi^{(0)} P^{n} P\big]\\ &=\big[\lim_{n \rightarrow \infty} \pi^{(0)} P^{n}\big] P\\ &=\pi P. \end{align*} We can explain the equation $ \pi=\pi P$ intuitively: Suppose that $X_n$ has distribution $\pi$. As we saw before, $\pi P$ gives the probability distribution of $X_{n+1}$. If we have $ \pi=\pi P$, we conclude that $X_n$ and $X_{n+1}$ have the same distribution. In other words, the chain has reached its steady-state (limiting) distribution. We can equivalently write $\pi=\pi P$ as \begin{align*} \pi_j= \sum_{k \in S} \pi_k P_{kj}, \; \textrm{ for all }j \in S. \end{align*} The righthand side gives the probability of going to state $j$ in the next step. When we equate both sides, we are implying that the probability of being in state $j$ in the next step is the same as the probability of being in state $j$ now.

---

Example
Consider a Markov chain in Example 11.12: a Markov chain with two possible states, $S=\{0,1\}$, and the transition matrix \begin{equation} P = \begin{bmatrix} 1-a & a \\[5pt] b & 1-b \end{bmatrix}, \end{equation} where $a$ and $b$ are two real numbers in the interval $[0,1]$ such that $0 \lt a+b \lt 2$. Using $$ \pi=\pi P,$$ find the limiting distribution of this Markov chain.

---

We now summarize the above discussion in the following theorem. In practice, if we are given a finite irreducible Markov chain with states $0,1,2, \cdots, r$, we first find a stationary distribution. That is, we find a probability distribution $\pi$ that satisfies \begin{align*} & \pi_j= \sum_{k \in S} \pi_k P_{kj}, \quad \textrm{ for all }j \in S,\\ &\sum_{j \in S} \pi_j=1. \end{align*} In this case, if the chain is also aperiodic, we conclude that the stationary distribution is a limiting distribution.

---

Example
Consider the Markov chain shown in Figure 11.14.

1. Is this chain irreducible?
2. Is this chain aperiodic?
3. Find the stationary distribution for this chain.
4. Is the stationary distribution a limiting distribution for the chain?

---

Countably Infinite Markov Chains:

When a Markov chain has an infinite (but countable) number of states, we need to distinguish between two types of recurrent states: positive recurrent and null recurrent states.

Remember that if state $i$ is recurrent, then that state will be visited an infinite number of times (any time that we visit that state, we will return to it with probability one in the future). We previously defined $r_i$ as the expected number of transitions between visits to state $i$. Consider a recurrent state $i$. If $r_i \lt \infty$, then state $i$ is a positive recurrent state. Otherwise, it is called null recurrent.

How do we use the above theorem? Consider an infinite Markov chain $\{X_n, n=0,1,2,...\}$, where $X_n \in S=\{0,1,2, \cdots\}$. Assume that the chain is irreducible and aperiodic. We first try to find a stationary distribution $\pi$ by solving the equations \begin{align*} &\pi_j= \sum_{k=0}^{\infty} \pi_k P_{kj}, \quad \textrm{ for }j=0,1,2, \cdots,\\ &\sum_{j=0}^{\infty} \pi_j=1. \end{align*} If the above equations have a unique solution, we conclude that the chain is positive recurrent and the stationary distribution is the limiting distribution of this chain. On the other hand, if no stationary solution exists, we conclude that the chain is either transient or null recurrent, so \begin{align*} \lim_{n \rightarrow \infty} P(X_n=j |X_0=i)=0, \textrm{ for all }i,j. \end{align*}

---

Example
Consider the Markov chain shown in Figure 11.15. Assume that $0 \lt p \lt\frac{1}{2}$. Does this chain have a limiting distribution?

---