Convergence to equilibrium for ergodic chains

We have discussed the existence and uniqueness of a stationary distribution for a Markov Chain in Long run behavior of Markov Chains. We have also shown that in a finite Markov Chain, if for some $i$ the limits

$$(p^n{)}_{ij}\to {\pi }_j$$

then the limiting distribution it’s also stationary. We now investigate the conditions needed for the convergence to the (unique) stationary distribution.

First a brief summary:

If $P$ is recurrent then there exists at least one invariant measure. If we add irreducibility, then using the lemma for invariant measure on irreducible chains, the invariant measure is unique up to a scaling factor.

These results rely on the vector ${\gamma }^k$, which is normalizable if the chain is positive recurrent for a state $k$, since ${\sum }_i{\gamma }_i^k={\mathbb{E}}_k[{\tau }_k^{+}]$, also an irreducible chain is positive recurrent iff it admits an invariant distribution. (An invariant measure is not sufficient, the conterexample is the symmetric r.w. in Z with invariant measure ${\lambda }_i=1$, the chain is null recurrent.)

Theorem Let $P$ be an ergodic chain (irreducible, aperiodic and positive recurrent), then for any starting distribution $\lambda$, for all $i,j$

$$P(X_n=i)\stackrel{n\to \infty }{\to }{\pi }_i$$

Proof The main idea is coupling (by Doblin 1937). Let $(X_n{)}_{n\ge 0}\sim Markov(\lambda ,P)$ and $(Y_n{)}_{n\ge 0}\sim Markov(\pi ,P)$

Fix a reference state $b\in I$, and define the stopping time

$$T:=\inf \{n\ge 0:X_n=Y_n=b\}$$

Step 1 We show that $P(T<\infty )=1$, for this we need both irreducibility (obvious) and also aperiodicity (less obvious). Consider the process $W_n:=(X_n,Y_n)$ with state space $I\times I$, and transition probabilties

$${\tilde{p}}_{(i,j)(k,l)}=p_{ij}{p}_{kl}$$

and initial distribution ${\mu }_{(ij)}={\lambda }_i{\pi }_j$. Since $P$ is aperiodic, for all state $i,j,k,l$ we have

$$({\tilde{P}}^n{)}_{(i,j)(k,l)}=(P^n{)}_{ij}(P^n{)}_{kl}>0$$

this follows from the property of Hadamard’s product: $(A\odot B{)}^n=A^n\odot B^n$ for $n$ large enough, so that $\tilde{P}$ is irreducibile. Also, one can check that ${\tilde{\pi }}_{(i,j)}:={\pi }_i{\pi }_j$ is an invariant distribution, so that $W_n$ is also positive recurrent.

We have a recurrent irreducibile markov chain, this means that for any initial distribution every state is visited a.s., in particular the state $(b,b)$, so that

$$P(T<\infty )=1$$

and the chains meet a.s.

Now the magick trick

$$P(X_n=j)=P(X_n=j,n\ge T)+P(X_n=j,n<T)$$ $$=P(Y_n=j,n\ge T)+P(X_n=j,n<T)+P(Y_n=j,n<T)-P(Y_n=j,n<T)$$ $$=P(Y_n=j)+P(X_n=j,n<T)-P(Y_n=j,n<T)$$ $$={\pi }_j+P(X_n=j,n<T)-P(Y_n=j,n<T)$$

the last two terms tend to zero when $n\to \infty$, since $T$ is finite a.s:

$$P(X_n=j,n<T)\le P(n<T)\stackrel{n\to \infty }{\to }0$$

so that

$$P(X_n=j)\stackrel{n\to \infty }{\to }{\pi }_j\square$$