In this section, we study some of the deepest and most interesting parts of the theory of Markov chains, involving two different but complementary ideas: stationary distributions and limiting distributions. The theory of renewal processes plays a critical role.

As usual, our starting point is a (time homogeneous) Markov chain $X=\left(\begin{array}{c}X_{0}\\ X_{1}\\ X_{2}\\ \end{array}\right)$ with countable state space $S$ and transition probability matrix $P$.

Let $y\in S$ and let $n\in $. We will denote the number of visits to $y$ during the first $n$ time units by

$$N_{y, n}=\sum_{i=1}^{n} (X_{i}=y)$$Note that $N_{y, n}\to N_{y}$ as $n\to \infty $, where

$$N_{y}=\sum_{i=1}^{\infty} (X_{i}=y)$$is the total number of visits to $y$, one of the important random variables that we studied in the section on Transience and Recurrence. Next we denote the time of the $(n)$ visit to $y$ by

$$T_{y, n}=\min\{N_{y, k}=n\mid N_{y, k}=n\}$$where as usual, we define $\mathrm{min}(\emptyset )=\infty $. Note that $T_{y, 1}$ is the time of the first visit to $y$, which we denoted simply by $T_{y}$ in the section on Transience and Recurrence. Recall also the definition of the hitting probability:

$$H(x, y)=(T_{y}< \infty , X_{0}=x)\text{,\hspace{1em}}\left(\begin{array}{c}x\\ y\end{array}\right)\in S^{2}$$Suppose that $y$ is recurrent and that $X_{0}=x$. Use the Markov and time-homogeneity properties to argue that

- If $x=y$, then the successive visits to $y$ form a renewal process.
- If $x\neq y$ but $x\to y$, then the successive visits to $y$ form a delayed renewal process.

Thus, $\{T_{y, n}\colon n\in \}$ is the sequence of arrival times and $\{N_{y, n}\colon n\in \}$ is the associated sequence of counting variables. The corresponding renewal function is

$$G_{n}(x, y)=(N_{y, n}, X_{0}=x)=\sum_{k=1}^{n} P^{k}(x, y)\text{,\hspace{1em}}n\in \mathbb{N}$$Note that $G_{n}(x, y)\to G(x, y)$ as $n\to \infty $ where $G$ is the potential matrix that we studied previously. This matrix gives the expected total number visits to $y$ starting at $x$:

$$G(x, y)=(N_{y}, X_{0}=x)=\sum_{k=1}^{\infty} P^{k}(x, y)\text{,\hspace{1em}}\left(\begin{array}{c}x\\ y\end{array}\right)\in S^{2}$$The limit theorems of renewal theory can now be used to explore the limiting behavior of the Markov chain. Let $\mu (y)=(T_{y}, X_{0}=y)$ denote the mean return time to state $y$, starting in $y$. In the following three exercises, we assume again that $y$ is recurrent, and we interpret $\frac{1}{\infty}=0$.

Use the strong law of large numbers for renewal theory to show that

$$(\frac{N_{y, n}}{n}\to \frac{1}{\mu (y)}\text{\hspace{0.5em}as \hspace{0.5em}}n\to \infty , X_{0}=x)=H(x, y)$$Use the elementary renewal theorem to show that

$$\frac{1}{n}\sum_{k=1}^{n} P^{k}(x, y)\to \frac{H(x, y)}{\mu (y)}\text{\hspace{0.5em}as \hspace{0.5em}}n\to \infty $$Suppose in addition that $y$ is aperiodic. Use the renewal theorem to show that

$$P^{n}(x, y)\to \frac{H(x, y)}{\mu (y)}\text{\hspace{0.5em}as \hspace{0.5em}}n\to \infty $$Note that $H(y, y)=1$ by the very definition of a recurrent state. Thus, when $x=y$, Exercise 2 gives convergence with probability 1, and the limit in Exercise 2, Exercise 3, and Exercise 4 is $\frac{1}{\mu (y)}$. By contrast, we already know the corresponding limiting behavior when $y$ is transient, since the number of visit to $y$ is finite with probability 1, and the expected number of visits to $y$ is finite.

Suppose that $y$ is transient. Show that for every $x$,

- $(\frac{N_{y, n}}{n}\to 0\text{\hspace{0.5em}as \hspace{0.5em}}n\to \infty , X_{0}=x)=1$.
- $\frac{1}{n}\sum_{k=1}^{n} P^{k}(x, y)\to 0$ as $n\to \infty $
- $P^{n}(x, y)\to 0$ as $n\to \infty $

On the other hand, the return time to $y$ is infinite with positive probability, by the very definition of a transient state. Thus $\mu (y)=\infty $, and thus, the results in parts (b) and (c) agree with Exercise 3 and Exercise 4, respectively. In particular, Exercise 3, which is our fundamental limiting result in many ways, holds for any states $x$ and $y$.

Clearly there is a fundamental dichotomy in terms of the limiting behavior of the chain, depending on whether the mean return time to a given state is finite or infinite. Thus, state $x$ is said to be positive recurrent if $\mu (x)< \infty $.

Show that if $x$ is positive recurrent, then $x$ is recurrent. That is, note that if $(T_{x}, X_{0}=x)< \infty $ then $P(T_{x}< \infty , X_{0}=x)=1$.

On the other hand, it is possible to have $(T_{x}< \infty , X_{0}=x)=1$, so that $x$ is recurrent, and also $(T_{x}, X_{0}=x)=\infty $, so that $x$ is not positive recurrent. (A random variable can be finite with probability 1, but can have infinite mean.) In such a case, $x$ is said to be null recurrent. Note that if $y$ is positive recurrent, then the limits in Exercise 2, Exercise 3, and Exercise 4 are positive if $x$ leads to $y$ and 0 otherwise. If $y$ is null recurrent or transient, the limits in Exercise 2, Exercise 3, and Exercise 4 are 0.

Like recurrence/transience, and period, the null/positive recurrence property is a class property.

Show that if $x$ is positive recurrent and $(x, y)$ then $y$ is positive recurrent.

- Suppose that $x$ is positive recurrent and $(x, y)$. Recall that $y$ is recurrent and $(y, x)$.
- Conclude that there exist positive integers $i$ and $j$ such that $P^{i}(x, y)> 0$ and $P^{j}(y, x)> 0$
- Show that for every positive integer $k$, $P^{(i+j+k)}(y, y)\ge P^{j}(y, x)P^{k}(x, x)P^{i}(x, y)$
- Average over $k$ from 1 to $n$ to conclude that $\frac{G_{n}(y, y)}{n}-\frac{G_{i+j}(y, y)}{n}\ge P^{j}(y, x)\frac{G_{n}(x, x)}{n}P^{i}(x, y)$.
- Let $n\to \infty $ and use Exercise 3 to show that $\frac{1}{\mu (y)}\ge P^{j}(y, x)\frac{1}{\mu (x)}P^{i}(x, y)$
- Finally, conclude that $\mu (y)< \infty $.

Thus, the terms positive recurrent and null recurrent can be applied to equivalence classes (under the *to and from* equivalence relation), as well as individual states. When the chain is irreducible, the terms can be applied to the chain as a whole.

Suppose that $A$ is a finite, closed set of states. Show that $A$ contains a positive recurrent state.

- Fix a state $x\in A$ and note that $\sum_{y\in A} P^{k}(x, y)=1$ for every $k\in $ since $A$ is closed.
- Average over $k$ from 1 to $n$ to obtain $\sum_{y\in A} \frac{G^{n}(x, y)}{n}=1$ for every $n\in $. Note that the change in the order of summation is justified since both sums are finite.
- Assume now that all states in $A$ are transient or null recurrent. Let $n\to \infty $ to conclude that $0=1$. Again, justify the interchange of sum and limit by the fact that $A$ is finite.

Suppose again that $A$ is a finite, closed set of states. Show that $A$ contains no null recurrent states.

- Let $x\in A$ and let $B$ denote the equivalence class containing $x$. Show that $B\subseteq A$ since $A$ is closed.
- Suppose that $B$ is recurrent. Note that $B$ is closed and finite and hence must have a positive recurrent state.
- Conclude that either $B$ (and hence $x$) is positive recurrent or transient.

Suppose that $A$ is a finite, closed, and irreducible set of states. Show that $A$ is a positive recurrent equivalence class.

- We already know that $A$ is a recurrent equivalence class, from our study of transience and recurrence.
- From the previous exercise, $A$ is positive recurrent.

In particular, a Markov chain with a finite state space cannot have null recurrent states; every state must be transient or positive recurrent.

Returning to the limiting behavior, suppose that the chain $X$ is irreducible, so that either all states are transient, all states are null recurrent, or all states are positive recurrent. From Exercise 3 and Exercise 4, if the chain is transient or if the chain is recurrent and aperiodic, then

$$P^{n}(x, y)\to \frac{1}{\mu (y)}\text{\hspace{0.5em}as \hspace{0.5em}}n\to \infty \text{\hspace{0.5em}for any \hspace{0.5em}}x\in S$$Of course in the transient case and in the null recurrent, aperiodic case, the limit is 0. Only in the positive recurrent, aperiodic case is the limit positive; in this case, the chain is said to ergodic. In all of these cases, the limit is independent of the initial state $x$. In the ergodic case, as we will see, $X_{n}$ has a limiting distribution as $n\to \infty $ that is independent of the initial distribution.

The behavior when the chain is periodic with period
$d$ is a bit more complicated, but we can understand this behavior by considering the
$d$-step chain
$\left(\begin{array}{c}X_{0}\\ X_{d}\\ X_{2d,}\end{array}\right)$
that has transition matrix
$P^{d}$.
Essentially, this allows us to trade *periodicity* (one form of complexity) for *reducibility* (another form of complexity). Specifically, recall that the
$d$-step chain is aperiodic but has
$d$ equivalence classes
$\left(\begin{array}{c}A_{0}\\ A_{1}\\ \\ A_{d-1}\end{array}\right)$;
and these are the cyclic classes of original chain
$X$.

Note that every single step for the $d$-step chain corresponds to $d$ steps for the original chain. Thus, show that the mean return time to state $x$ for the $d$-step chain is $\mu _{d}(x)=\frac{\mu (x)}{d}$.

Use the result of the previous exercise and the cyclic behavior of the chain to prove the following results, where the indices $i$, $j$, and $k$ are in $\{0, 1, , d-1\}$:

- $P^{(nd+k)}(x, y)\to \frac{d}{\mu (y)}$ as $n\to \infty $ if $x\in A_{i}$ and $y\in A_{j}$ for some $i$ and $j$ with $j=(i+k)\mod d$
- $P^{(nd+k)}(x, y)\to 0$ as $n\to \infty $ in all other cases.

Show that if the $y$ is null recurrent (or of course transient) then regardless of the period of $y$, $P^{n}(x, y)\to 0$ as $n\to \infty $ for every $x\in S$.

Our next goal is to see how the limiting behavior is related to invariant distributions. Suppose that $f$ is a probability density function on the state space $S$. Recall that $f$ is invariant for $P$ (and for the chain $X$) if $fP=f$. It follows immediately that $fP^{n}=f$ for every $n\in \mathbb{N}$. Thus, if $X_{0}$ has probability density function $f$ then so does $X_{n}$ for each $n\in \mathbb{N}$, and hence $X$ is a sequence of identically distributed random variables.

Suppose that $(g, S, \left[0 , \infty \right))$ is left-invariant for $P$, and let $C=\sum_{x\in S} g(x)$. If $0< C< \infty $ then $f$ defined by $f(x)=\frac{g(x)}{C}$ for $x\in S$ is an invariant probability density function.

Suppose that $g$ is a nonnegative function on $S$ that is left-invariant for $P$ and satisfies $\sum_{x\in S} g(x)< \infty $. Show that

$$g(y)=\frac{1}{\mu (y)}\sum_{x\in S} g(x)H(x, y)$$- Recall again that $gP^{k}=g$ for every $k\in \mathbb{N}$ since $g$ is left-invariant for $P$.
- Average the result in (a) over $k$ from 1 to $n$ to obtain $g\frac{G_{n}}{n}=g$ for each $n\in $.
- Let $n\to \infty $ in (b). Use the dominated convergence theorem to interchange the limit with the sum. This is the point where we need $g$ to have a finite sum.
- Use the result in Exercise 3.

Note that if $y$ is transient or null recurrent, then $g(y)=0$. Thus, an invariant probability distribution must be concentrated on the positive recurrent states.

Suppose now that the chain is irreducible. If the chain is transient or null recurrent, then the only nonnegative functions that are left-invariant for $P$ are functions that satisfy $\sum_{x\in S} g(x)=\infty $ and the function that is identically 0: $g(x)=0$ for all $x\in S$. In particular, the chain does not have an invariant distribution. On the other hand, if the chain is positive recurrent, then $H(x, y)=1$ for all $x$ and $y$. Thus, the only possible invariant probability density function is the function $f$ given by $f(x)=\frac{1}{\mu (x)}$ for $x\in S$. Any other nonnegative function $g$ that is left-invariant for $P$ and has finite sum, is a multiple of $f$ (and indeed the multiple is sum of the values). Our next goal is to show that $f$ really is an invariant probability density function.

Suppose that $X$ is an irreducible, positive recurrent chain. Show that the function $f$ given by $f(x)=\frac{1}{\mu (x)}$ for $x\in S$ is an invariant probability density function for $X$.

- Let $A$ be a finite subset of $S$. Show that $\sum_{y\in A} \frac{1}{n}G_{n}(x, y)\le 1$ for every $x\in S$.
- Let $n\to \infty $ in (a) and use Exercise 3 to conclude that $\sum_{y\in A} f(y)\le 1$. The interchange of limit and sum is justified since $A$ is finite.
- Conclude now that $C\le 1$ where $C=\sum_{x\in S} f(x)$ is the normalizing constant. Note also that $C> 0$ since the chain is positive recurrent.
- Show that $\sum_{y\in A} \frac{1}{n}G_{n}(x, y)P(y, z)\le \frac{1}{n}G_{n+1}(x, z)$ for every $x\in S$ and $z\in S$.
- Let $n\to \infty $ to conclude that $\sum_{y\in A} f(y)P(y, z)\le f(z)$ for every $z\in S$.
- Conclude now that $\sum_{y\in S} f(y)P(y, z)\le f(z)$ for every $z\in S$.
- In the previous part, suppose that strict inequality holds for some for some $z\in S$. Conclude that $\sum_{z\in S} \sum_{y\in S} f(y)P(y, z)< \sum_{z\in S} f(z)$.
- Interchange the order of summation on the left in the previous inequality to obtain the contradiction $\sum_{y\in S} f(y)< \sum_{z\in S} f(z)$.
- Conclude that $f$ is left-invariant for $P$.
- Conclude that $\frac{f}{C}$ is an invariant probability density function.
- By the uniqueness result noted earlier, conclude that $\frac{f}{C}=f$ so that in fact $C=1$.

In summary, an irreducible, positive recurrent Markov chain
$X$ has a unique invariant probability density function
$f$ given by
$f(x)=\frac{1}{\mu (x)}$
for
$x\in S$.
We also now have a *test* for positive recurrence. An irreducible Markov chain
$X$ is positive recurrent if and only if there exists a nonnegative function
$g$ on
$S$ that is left-invariant for
$P$, not identically 0, and satisfies
$\sum_{x\in S} g(x)< \infty $
(and then, of course, normalizing
$g$ would give
$f$).

Consider now a general Markov chain $X$ on $S$. If $X$ has no positive recurrent states, then as noted earlier, there are no invariant distributions. Thus, suppose that $X$ has a collection of positive recurrent equivalence classes $\{A_{i}\colon i\in I\}$ where $I$ is a nonempty, countable index set. The chain restricted to $A_{i}$ is irreducible and positive recurrent for each $i\in I$, and hence has a unique invariant probability density function $f_{i}$ on $A_{i}$ given by

$$f_{i}(x)=\frac{1}{\mu (x)}\text{,\hspace{1em}}x\in A_{i}$$Show that $f$ is an invariant probability density function for $X$ if and only if $f$ has the form $f(x)=p_{i}f_{i}(x)$ for $x\in A_{i}$ and $i\in I$ where $\{p_{i}\colon i\in I\}$ is a probability density function on the index set $I$.

Consider again the general two-state chain on $S=\{0, 1\}$ with transition probability matrix given below, where $p$ and $q$ are parameters with $0< p< 1$ and $0< q< 1$.

$$P=\begin{pmatrix}1-p & p\\ q & 1-q\end{pmatrix}$$- Find the invariant distribution.
- Find the mean return time to each state.
- Find $\lim_{n\to \infty}P^{n}$ without having to go to the trouble of diagonalizing $P$, as we did in the Introduction.

Consider a Markov chain with state space $S=\{a, b, c, d\}$ and transition matrix $P$ given below:

$$P=\begin{pmatrix}1/3 & 2/3 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 1/4 & 1/4 & 1/4 & 1/4\end{pmatrix}$$- Draw the state diagram.
- Determine the equivalent classes and classify each as transient or positive recurrent.
- Find all invariant probability density functions.
- Find the mean return time to each state.
- Find $\lim_{n\to \infty}P^{n}$.

Consider a Markov chain with state space $S=\{1, 2, 3, 4, 5, 6\}$ and transition matrix $P$ given below:

$$P=\begin{pmatrix}0 & 0 & 1/2 & 0 & 1/2 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ 1/4 & 0 & 1/2 & 0 & 1/4 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1/3 & 0 & 2/3 & 0\\ 0 & 1/4 & 1/4 & 1/4 & 0 & 1/4\end{pmatrix}$$- Sketch the state graph.
- Find the equivalence classes and classify each as transient or positive recurrent.
- Find all invariant probability density functions.
- Find the mean return time to each state.
- Find $\lim_{n\to \infty}P^{n}$.

Consider a Markov chain with state space $S=\{1, 2, 3, 4, 5, 6\}$ and transition matrix $P$ given below:

$$P=\begin{pmatrix}1/2 & 1/2 & 0 & 0 & 0 & 0\\ 1/4 & 3/4 & 0 & 0 & 0 & 0\\ 1/4 & 0 & 1/2 & 1/4 & 0 & 0\\ 1/4 & 0 & 1/2 & 1/2 & 0 & 1/2\\ 0 & 0 & 0 & 0 & 1/2 & 1/2\\ 0 & 0 & 0 & 0 & 1/2 & 1/2\end{pmatrix}$$- Sketch the state graph.
- Find the equivalence classes and classify each as transient or positive recurrent.
- Find all invariant probability density functions.
- Find the mean return time to each state.
- Find $\lim_{n\to \infty}P^{n}$.

Consider the Markov chain with state space $S=\{1, 2, 3, 4, 5, 6, 7\}$ and transition matrix $P$ given below:

$$P=\begin{pmatrix}0 & 0 & 1/2 & 1/4 & 1/4 & 0 & 0\\ 0 & 0 & 1/3 & 0 & 2/3 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1/3 & 2/3\\ 0 & 0 & 0 & 0 & 0 & 1/2 & 1/2\\ 0 & 0 & 0 & 0 & 0 & 3/4 & 1/4\\ 1/2 & 1/2 & 0 & 0 & 0 & 0 & 0\\ 1/4 & 3/4 & 0 & 0 & 0 & 0 & 0\end{pmatrix}$$- Sketch the state digraph, and show that the chain is irreducible with period 3.
- Identify the cyclic classes.
- Find the invariant probability density function.
- Find the mean return time to each state.
- Find $\lim_{n\to \infty}P^{(3n)}$.
- Find $\lim_{n\to \infty}P^{(3n+1)}$.
- Find $\lim_{n\to \infty}P^{(3n+2)}$.

Read the discussion of invariant distributions and limiting distributions in the Ehrenfest chains, and work the problems.

Read the discussion of invariant distributions and limiting distributions in the Bernoulli-Laplace chain, and work the problems.

Read the discussion of positive recurrence and invariant distributions for the reliability chains, and work the problems.

Read the discussion of positive recurrence and limiting distributions for the birth-death chain, and work the problems.

Read the discussion of positive recurrence and for the queuing chains, and work the problems.

Read the discussion of positive recurrence and limiting distributions for the random walks on graphs, and work the problems.