11.2.6 Stationary and Limiting Distributions

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*}
  • Solution
      1. For $n=1$, we have \begin{align*} P^1&=\begin{bmatrix} 1-a & a \\[5pt] b & 1-b \end{bmatrix}\\ &= \frac{1}{a+b} \begin{bmatrix} b & a \\[5pt] b & a \end{bmatrix}+\frac{1-a-b}{a+b} \begin{bmatrix} a & -a \\[5pt] -b & b \end{bmatrix}. \end{align*} Assuming that the statement of the problem is true for $n$, we can write $P^{n+1}$ as \begin{align*} P^{n+1}=P^{n} P&=\frac{1}{a+b} \left(\begin{bmatrix} b & a \\[5pt] b & a \end{bmatrix}+(1-a-b)^n \begin{bmatrix} a & -a \\[5pt] -b & b \end{bmatrix}\right) \cdot \begin{bmatrix} 1-a & a \\[5pt] b & 1-b \end{bmatrix}\\ &=\frac{1}{a+b} \begin{bmatrix} b & a \\[5pt] b & a \end{bmatrix}+\frac{(1-a-b)^{n+1}}{a+b} \begin{bmatrix} a & -a \\[5pt] -b & b \end{bmatrix}, \end{align*} which completes the proof.
      2. By assumption $0 \lt a+b \lt 2$, which implies $-1 \lt 1-a-b \lt 1$. Thus, \begin{align*} \lim_{n \rightarrow \infty}(1-a-b)^n=0. \end{align*} Therefore, \begin{align*} \lim_{n \rightarrow \infty} P^n=\frac{1}{a+b} \begin{bmatrix} b & a \\[5pt] b & a \end{bmatrix}. \end{align*}
      3. We have \begin{align*} \lim_{n \rightarrow \infty} \pi^{(n)}&= \lim_{n \rightarrow \infty} \left[\pi^{(0)} P^n\right]\\ &= \pi^{(0)} \lim_{n \rightarrow \infty} P^n\\ &= \begin{bmatrix} \alpha & 1-\alpha \end{bmatrix} \cdot \frac{1}{a+b} \begin{bmatrix} b & a \\[5pt] b & a \end{bmatrix}\\ &= \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$.
Limiting Distributions

The probability distribution $\pi=[\pi_0, \pi_1, \pi_2, \cdots ]$ is called the limiting distribution of the Markov chain $X_n$ if \begin{align*} \pi_j=\lim_{n \rightarrow \infty} P(X_n=j |X_0=i) \end{align*} for all $i, j \in S$, and we have \begin{align*} \sum_{j \in S} \pi_j=1. \end{align*}
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.
  • Solution
    • We can use the method of the law of total probability that we explained before to find the mean return times (Example 11.11). We can also find $r_0$ and $r_1$ directly as follows:

      Let $R$ be the first return time to state $0$, i.e., $r_0=E[R|X_0=0]$. If $X_0=0$, then $X_1=0$ with probability $1-a$, and $X_1=1$ with probability $a$. Thus, using the law of total probability, and assuming $X_0=0$, we can write

      \begin{align*} r_0&=E[R|X_1=0, X_0=0]P(X_1=0|X_0=0)+E[R|X_1=1, X_0=0]P(X_1=1|X_0=0)\\ &=E[R|X_1=0] \cdot (1-a)+ E[R|X_1=1] \cdot a. \end{align*} If $X_1=0$, then $R=1$, so \begin{align*} E[R|X_1=0]=1. \end{align*} If $X_1=1$, then $R \sim 1+Geometric(b)$, so \begin{align*} E[R|X_1=1]&=1+E[Geometric(b)]\\ &=1+\frac{1}{b}. \end{align*} We conclude \begin{align*} r_0&=E[R|X_1=0]P(X_1=0|X_0=0)+E[R|X_1=1]P(X_1=1|X_0=0)\\ &=1 \cdot (1-a)+ \left(1+\frac{1}{b}\right) \cdot a\\ &=\frac{a+b}{b}. \end{align*} Similarly, we can obtain the mean return time to state $1$: \begin{align*} r_1=\frac{a+b}{a}. \end{align*} We notice that for this example, the mean return times are given by the inverse of the limiting probabilities. In particular, we have \begin{align*} r_0=\frac{1}{\pi_0}, \quad r_1=\frac{1}{\pi_1}. \end{align*} As we will see shortly, this is not a coincidence. In fact, we can explain this intuitively. The larger the $\pi_i$ is, the smaller the $r_i$ will be. For example, if $\pi_i=\frac{1}{4}$, we conclude that the chain is in state $i$ one-fourth of the time. In this case, $r_i=4$, which means that on average it takes the chain four time units to go back to state $i$.


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.
  • Solution
    • Let $\pi=[\pi_0, \pi_1]$. Then, we can write \begin{align*} [\pi_0, \pi_1]=\pi P &= [\pi_0, \pi_1] \begin{bmatrix} 1-a & a \\[5pt] b & 1-b \end{bmatrix}\\ &=\begin{bmatrix} \pi_0 (1-a)+\pi_1 b & \pi_0 a+\pi_1 (1-b) \end{bmatrix}. \end{align*} We obtain two equations; however, they both simplify to \begin{align*} \pi_0 a=\pi_1 b. \end{align*} We remember that $\pi$ must be a valid probability distribution, i.e., $\pi_0+\pi_1=1$. Thus, we can obtain a unique solution, i.e., \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*} which is the same answer that we obtained previously.


We now summarize the above discussion in the following theorem.
Consider a finite Markov chain $\{X_n, n=0,1,2,...\}$ where $X_n \in S=\{0,1,2, \cdots, r\}$. Assume that the chain is irreducible and aperiodic. Then,
  1. The set of equations \begin{align*} &\pi= \pi P,\\ &\sum_{j \in S} \pi_j=1 \end{align*} has a unique solution.
  2. The unique solution to the above equations is the limiting distribution of the Markov chain, i.e., \begin{align*} \pi_j=\lim_{n \rightarrow \infty} P(X_n=j |X_0=i), \end{align*} for all $i, j \in S$.
  3. We have \begin{align*} r_j=\frac{1}{\pi_j}, \quad \textrm{for all $j \in S$}, \end{align*} where $r_j$ is the mean return time to state $j$.
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.
MC-diagram-tek
Figure 11.14- A state transition diagram.
  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?
  • Solution
      1. The chain is irreducible since we can go from any state to any other states in a finite number of steps.
      2. Since there is a self-transition, i.e., $p_{11}>0$, we conclude that the chain is aperiodic.
      3. To find the stationary distribution, we need to solve \begin{align*} & \pi_1 =\frac{1}{4} \pi_1+\frac{1}{3} \pi_2+\frac{1}{2} \pi_3, \\ & \pi_2 =\frac{1}{2} \pi_1,\\ & \pi_3 =\frac{1}{4} \pi_1+\frac{2}{3} \pi_2+\frac{1}{2} \pi_3, \\ & \pi_1+\pi_2+\pi_3=1. \end{align*} We find \begin{align*} \pi_1 =\frac{3}{8}, \; \pi_2=\frac{3}{16}, \; \pi_3=\frac{7}{16}. \end{align*}
      4. Since the chain is irreducible and aperiodic, we conclude that the above stationary distribution is a limiting distribution.


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.

Let $i$ be a recurrent state. Assuming $X_0=i$, let $R_i$ be the number of transitions needed to return to state $i$, i.e., \begin{align*} R_i = \min \{n \geq 1: X_n=i \}. \end{align*} If $r_i=E[R_i |X_0=i] \lt \infty$, then $i$ is said to be positive recurrent. If $E[R_i |X_0=i]=\infty$, then $i$ is said to be null recurrent.
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. Then, one of the following cases can occur:
  1. All states are transient, and \begin{align*} \lim_{n \rightarrow \infty} P(X_n=j |X_0=i)=0, \textrm{ for all }i,j. \end{align*}
  2. All states are null recurrent, and \begin{align*} \lim_{n \rightarrow \infty} P(X_n=j |X_0=i)=0, \textrm{ for all }i,j. \end{align*}
  3. All states are positive recurrent. In this case, there exists a limiting distribution, $\pi=[\pi_0, \pi_1, \cdots ]$, where \begin{align*} \pi_j=\lim_{n \rightarrow \infty} P(X_n=j |X_0=i)>0, \end{align*} for all $i, j \in S$. The limiting distribution is the unique solution to 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*} We also have \begin{align*} r_j=\frac{1}{\pi_j}, \quad \textrm{for all $j=0,1,2, \cdots$}, \end{align*} where $r_j$ is the mean return time to state $j$.
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?
MC-diagram-inf-1
Figure 11.15 - A state transition diagram.
  • Solution
    • This chain is irreducible since all states communicate with each other. It is also aperiodic since it includes a self-transition, $P_{00}>0$. Let's write the equations for a stationary distribution. For state $0$, we can write \begin{align*} \pi_0 &=(1-p)\pi_0+(1-p) \pi_1, \end{align*} which results in \begin{align*} \pi_1 &=\frac{p}{1-p}\pi_0. \end{align*} For state $1$, we can write \begin{align*} \pi_1 &= p \pi_0+(1-p) \pi_2\\ &=(1-p) \pi_1+(1-p) \pi_2, \end{align*} which results in \begin{align*} \pi_2 &=\frac{p}{1-p}\pi_1. \end{align*} Similarly, for any $j \in \{1,2,\cdots \}$, we obtain \begin{align*} \pi_{j} &=\alpha \pi_{j-1}, \end{align*} where $\alpha=\frac{p}{1-p}$. Note that since $0 \lt p \lt \frac{1}{2}$, we conclude that $0 \lt \alpha \lt 1$. We obtain \begin{align*} \pi_{j} &=\alpha^j \pi_{0}, \quad \textrm{ for $j= 1,2,\cdots $ }. \end{align*} Finally, we must have \begin{align*} 1 &=\sum_{j=0}^{\infty} \pi_j\\ &= \sum_{j=0}^{\infty} \alpha^j \pi_0, &(\textrm{where } 0 \lt \alpha \lt 1)\\ &=\frac{1}{1-\alpha} \pi_0 &(\textrm{geometric series}). \end{align*} Thus, $\pi_0=1-\alpha$. Therefore, the stationary distribution is given by \begin{align*} \pi_{j} &= (1-\alpha) \alpha^j, \quad \textrm{ for $j= 0, 1,2,\cdots $ }. \end{align*} Since this chain is irreducible and aperiodic and we have found a stationary distribution, we conclude that all states are positive recurrent and $\pi=[\pi_0, \pi_1, \cdots ]$ is the limiting distribution.






The print version of the book is available through Amazon here.

Book Cover