Long run behavior of Markov Chains

Def A Markov Chain $(X_n{)}_{n\ge 0}$ is said to admin a limiting probability distribution if the following conditions are satisfied:

1. the limits

$$\underset{n\to \infty }{\lim }{P}_i(X_n=j)$$

exists for all states $i,j\in I$ and are indipendent from the starting state $i$, and 2.

$$\sum _{j\in I}\underset{n\to \infty }{\lim }{P}_i(X_n=j)=1$$

for all $i\in I$.

Remark Condition $2.$ is always satisfied in the case of a finite state space $I$, provided that the limits exists (codition $1.$) since we can exchange then limit and then (finite) summation.

For intuition, think of a finite Markov Chain with its transition matrix being an $n\times n$ stochastic matrix. What happens if we start from any vector $v_0$, and reapply the right matrix multiplication $v_{n+1}=v_{n}P$? in the limit $n\to \infty$ we expect $v_n$ to be in the eigenspace corresponding to the eigenvalue of greatest absulute value. But using Gershgorin cicle theorem it’s easy to see that the spectrum of a stochastic matrix is limited to value $1$, and such eigenvalue exists since in any stochastic matrix the vector $(1,1,1\dots {)}^T$ has eigenvalue $1$ (every row sums to one and $\sigma (P)=\sigma (P^T)$).

Then it’s natural to define the following:

Def (Stationary measure) We say that a measure $\lambda =({\lambda }_i:i\in I)$ is an invariant measure of the Markov Chain with transition matrix $P$ if it solved the LHE:

$$\lambda =\lambda P$$

if ${\sum }_i{\lambda }_i=1$ it’s called an invariant probability distribution.

We now show that if a finite Markov Chain admits a limiting probability distribution (even if it depends on the starting state $i$), then the limiting distribution is also stationary.

Theorem Let $I$ be finite. Suppose that for some $i\in I$ the following limits exists

$$P_i(X_n=j)=p_{ij}^{(n)}\to {\pi }_j\forall j\in I$$

then $\pi =({\pi }_i:i\in I)$ is an invariant distribution. Proof First we check that it’s normalized

$$\sum _{j\in I}{\pi }_j=\sum _{j\in I}\underset{n\to \infty }{\lim }{p}_{ij}^{(n)}=\underset{n\to \infty }{\lim }\sum _{j\in I}{p}_{ij}^{(n)}=1$$

and

$${\pi }_j=\underset{n\to \infty }{\lim }{p}_{ij}^{(n)}=\underset{n\to \infty }{\lim }\sum _{k\in I}{p}_{ik}^{(n-1)}{p}_{kj}=\sum _{k\in I}{p}_{kj}\underset{n\to \infty }{\lim }{p}_{ik}^{(n-1)}=\sum _{k\in I}{p}_{kj}{\pi }_j$$

where the exchanges are justified by the finiteness of the summation. $\square$

So in general if the state space is infinite, the limiting distribution are not stationary distribution. Consider the symmetric random walk in $\mathbb{Z}$, the limiting distribution are $p_{ij}^{(n)}\to 0$, which is stationary, but not a probability measure!

Other possibilities are:

• Stationary distribution may not be unique if the Markov chain is not irreducible, since any convex combination of each class is a new valid stationary distribution. Trivial example is $P=Id$ (any distribution is invariant). Another counterexample is if the chain is irreducible but transient: consider the one dimensional RW with transition probabilities $p\ne q$, then we have two stationary measures: ${\lambda }_i=1$ and ${\mu }_i=(p/q{)}^i$.
• Stationary distribution may not exist, (es. symmetric walk in $\mathbb{Z}$)
• Limiting distribution do not exist if the Markov chain is periodic, a trivial example is the MC with transition matrix

$$P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$$

What are the conditions such that the limiting distribution exists? When it’s unique? When does a stationary distribution exists? When it’s unique?

The best we can hope is that the limiting distribution exists, and it converges to the unique stationary distribution.

For a fixed state $k$, we define for each $i$ the expected time spent in $i$ between visits to $k$:

$${\gamma }_i^k:={\mathbb{E}}_k\left[\sum _{n=1}^{\infty }1(X_n=i,n\le {\tau }_k^{+})\right]$$

Oss Observe that

$$\sum _{i\in I}{\gamma }_i^k=1+\sum _{i\in I:i\ne k}{\mathbb{E}}_k[\text{ \# of visits to i before returning to }k]$$ $$=1+{\mathbb{E}}_k[T_k-1]={\mathbb{E}}_k[T_k]$$

Theorem (Existence of an invariant measure) Let $P$ be irreducible and recurrent. Then

1. ${\gamma }_k^k=1$
2. ${\gamma }^k=({\gamma }_i^k:i\in I)$ is invariant (i.e. satisfies ${\gamma }^k={\gamma }^{k}P$)
3. $0<{\gamma }_i^k<\infty$ for all $i\in I$.

Proof $1.$ It follows from the definition. $2.$ Exchanging the expectetion value (the exchange is justified by MON) we get:

$${\gamma }_i^k=\sum _{n=1}^{\infty }{P}_k(X_n=i,n\le {\tau }_k^{+})$$

Let’s check that ${\gamma }^k$ is invariant:

$$\sum _{i\in I}{\gamma }_i^k{p}_{ij}=\sum _{i\in I}\sum _{n=1}^{\infty }{P}_k(X_n=i,n\le {\tau }_k^{+})p_{ij}$$

now the event $\{n\le {\tau }_k^{+}\}$ depends only on information up to time $n-1$, since:

$$\{n\le {\tau }_k^{+}\}=\{X_1\ne k,X_2\ne k,\dots ,X_{n-1}\ne k\}$$

thus, using the Markov property

$$P_k(X_{n+1}=j|X_n=i,n\le {\tau }_k^{+})=P_k(X_{n+1}=j|X_n=i)=p_{ij}$$

using this identity

$$=\sum _{i\in I}\sum _{n=1}^{\infty }{P}_k[1(X_n=i,n\le {\tau }_k^{+})]P_k(X_{n+1}=j|X_n=i,n\le {\tau }_k^{+})$$ $$=\sum _{i\in I}\sum _{n=1}^{\infty }{P}_k(X_{n+1}=j,X_n=i,n\le {\tau }_k^{+})$$ $$=\sum _{n=1}^{\infty }{P}_k(X_{n+1}=j,n\le {\tau }_k^{+})$$ $$=\sum _{n=1}^{\infty }{P}_k(X_{n+1}=j,n+1\le {\tau }_k^{+})+\sum _{n=1}^{\infty }{P}_k(X_{n+1}=j,n={\tau }_k^{+})$$ $$={\gamma }_j^k-P_k(X_1=j,1\le {\tau }_k^{+})={\gamma }_j^k-p_{kj}$$

the other term is

$$\sum _{n=1}^{\infty }{P}_k(X_{n+1}=j|n={\tau }_k^{+})P_k(n={\tau }_k^{+})=p_{kj}\sum _{n=1}^{\infty }{P}_k(n={\tau }_k^{+})=p_{kj}$$

where ${\sum }_{n=1}^{\infty }{P}_k(n={\tau }_k^{+})=P_k({\tau }_k^{+}<\infty )=1$ since the chain is recurrent.

$3.$ Since the chain is irreducible, for each state $i$ there exists $n,m>0$ such that $p_{ik}^{(n)},p_{ki}^{(m)}>0$, then ${\gamma }^k={\gamma }^k{P}^{(n)}$ and ${\gamma }^k={\gamma }^k{P}^{(m)}$

$${\gamma }_i^k=\sum _{j\in I}{\gamma }_j^k{p}_{ji}^{(m)}\ge {\gamma }_k^k{p}_{ki}^{(m)}=p_{ki}^{(m)}>0$$ $$1={\gamma }_k^k=\sum _{j\in I}{\gamma }_j^k{p}_{jk}^{(n)}\ge {\gamma }_i^k{p}_{ik}^{(n)},{\gamma }_i^k\le \frac{1}{p_{ik}^{(n)}}<\infty$$

And our theorem is proven. $\square$

Clearly if we scale by a positive costant we get a new invariant mesure. If this invariant measure is normalizable, then we can find an invariant probability distribution. This is possibile if the chain is positive recurrent.

Let $P$ be irreducible. Then the following conditions are equivalent:

1. All states are positive recurrent.
2. Some state is positive recurrent.
3. There exists an invariant distribution $\pi$. Moreover, when $3.$ holds we have ${\pi }_i=\frac{1}{{\mathbb{E}}_i[{\tau }_i^{+}]}$

Proof $1.⟹2.$ is obvious. (we include this to show that positive recurrence is also a class property!). $2.⟹3.$ Call $k$ a recurrent state. Since a this state is recurrent and the chain irreducible, then the vector ${\gamma }^k$ is an invariant measure, and since $k$ is positive recurrent it’s also normalizalble, so that

$${\pi }_i:=\frac{{\gamma }_i^k}{{\mathbb{E}}_k[{\tau }_k^{+}]}$$

is an invariant distribution. $3.⟹1.$ Since $\pi$ is an invariant distribution

$$\sum _i{\pi }_i=1$$

so that there must exists at least one ${\pi }_k>0$. But since the chain i irreducibile this implies that $0<{\pi }_i<\infty$ for all $i\in I$. Choose any $k$ and set ${\lambda }_i:=\frac{{\pi }_i}{{\pi }_k}$, this is an invariant measure of an irreducible chain, so that

$${\lambda }_i\ge {\gamma }_i^k,\text{ for all }i$$

but then

$${\mathbb{E}}_k[{\tau }_k^{+}]=\sum _i{\gamma }_i^k\le \sum _i{\lambda }_i=\sum _i\frac{{\pi }_i}{{\pi }_k}=\frac{1}{{\pi }_k}<\infty \square$$

Theorem (Uniqueness of an invariant measure). Let $P$ be irreducible and let $\lambda$ be an invariant measure for $P$ with ${\lambda }_k=1$. Then ${\lambda }_i\ge {\gamma }_i^k$ for all $i\in I$. If $P$ is recurrent then $\lambda ={\gamma }^k$, so that the invariant measure is unique up to a positive constat facor (we set ${\lambda }_k=1$).

Proof For each $i\in I$ we have

$${\lambda }_i=\sum _j{\lambda }_j{p}_{ji}=p_{ki}+\sum _{j\ne k}{\lambda }_j{p}_{ji}$$

we use the same strategy in the proofs of Hitting probability and mean hitting times, repeated substitution:

$$=p_{ki}+\sum _{j\ne k}\left(p_{kj}+\sum _{z\ne k}{\lambda }_z{p}_{zj}\right)p_{ji}$$ $$=p_{ki}+\sum _{j\ne k}{p}_{kj}{p}_{ji}+R$$

where $R\ge 0$ is a positive quantity. By repeating this substitution one gets:

$$\ge P_k(X_1=i)+P_k(X_2=i,n\le {\tau }_k^{+})+\dots$$

taking the limit, and exchanging expected value and sum by (MON) on gets the definition of ${\gamma }_i^k$.

If in addition $P$ is also recurrent, then ${\gamma }^k$ is also stationary, we can define a new stationary measure

$$\mu :=\lambda -{\gamma }^k$$

(we can do this since $\lambda \ge {\gamma }^k$), but since they agree on state $k$ ${\mu }_k=0$, so by our previou theorem point $3.$ ${\mu }_i=0$ for all $i\in I$, so that $\lambda ={\gamma }^k$. $\square$