08 - Stationary Distributions of Markov Chains

Stationary Distribution

Let $\pi =({\pi }_i,i\in I)$ be a distribution on state space $I$

Let $P$ be a transition matrix then

$\pi$ is a Stationary Distribution, or Invariant Distribution, or Equilibrium Distribution of $P$ if

$$\pi P=\pi$$

In other words for all $j\in I$ then

$${\pi }_j=\sum _i{\pi }_i{p}_{ij}$$

so $\pi$ is a left eigenvector for matrix $P$ with eigenvalue $1$

Stationarity Implies Time-Invariance

Let $\pi =({\pi }_i,i\in I)$ be a distribution on state space $I$ with transition matrix $P$

If $X_0$ has distribution $\pi$ then

$$X_n\text{ has distribution }\pi P^n$$

Furthermore if $\pi$ is a Stationary Distribution

$$X_n\text{ has distribution }\pi \text{ for all }n$$

Stationary Distribution of a Random Walk on a Graph

Consider irreducible random walk on a graph with vertex degrees $d_i$ then

Stationary distribution is

$${\pi }_i=\frac{d_i}{\sum _j{d}_j}$$

Note that this can be verified by checking $dP=d$ where $d$ is the degree vector

Stationary Distribution of a One-Dimensional Random Walk

For the random walk on $\{0,1,2,\dots \}$ with

$$\begin{array}{r}{p}_{0,0}=q,p_{i,i+1}=p,p_{i,i-1}=q\text{ for }i\ge 1\end{array}$$

• $p\ge q$: No Stationary Distribution

• $p<q$: Geometric with Parameter $1-\frac{p}{q}$

$${\pi }_i=\left(1-\frac{p}{q}\right){\left(\frac{p}{q}\right)}^i$$

Stationary Distribution from Mean Return Times lemma

Let $P$ be positive recurrent with stationary distribution $\pi =({\pi }_i,i\in I)$ then

$${\pi }_i\text{ is proportional to }\frac{1}{m_i}$$

Stationary Probability Equals Inverse Mean Return Time lemma

Let $\pi$ be any stationary distribution then

$${\pi }_i=\frac{1}{m_i}$$

Proof

Suppose $\pi$ is stationary for $P$
Let $X$ be a Markov Chain with initial distribution $\pi$ and transition matrix $P$

As stationary then

$$\mathbb{P}(X_n=i)={\pi }_i\text{ for all }n$$

and

$$\begin{array}{rl}\frac{\mathbb{E}[V_n(i)]}{n}& =\frac{1}{n}\sum _{r=0}^{n-1}\mathbb{E}[1(X_n=i)]\\ & =\frac{1}{n}\sum _{r=0}^{n-1}\mathbb{P}(X_n=i)\\ & ={\pi }_i\end{array}$$

By Ergodic Theorem then for any $ϵ$

$$\mathbb{P}\left(\left|\frac{V_n(i)}{n}-\frac{1}{m_i}\right|<ϵ\right)<ϵ$$

for large $n$

As $\frac{V_n(i)}{n}$ is bounded between $0$ and $1$ then

$$\frac{\mathbb{E}[V_n(i)]}{n}\to \frac{1}{m_i}\text{ as }n\to \infty$$

Hence

$${\pi }_i=\frac{1}{m_i}$$

Time-Reversible Chain

Let $X\sim \mathrm{Markov}(\pi ,P)$ and $Y\sim \mathrm{Markov}(\pi ,Q)$ where $Y$ is the time-reversal of chain $X$

Chain is reversible / time-reversible / time-reversible in equilibrium if

$$P=Q$$

Reversibility of Random Walks on Trees and Graphs

Any irreducible chain whose transition graph is a tree (no cycles) is reversible
In particular, the random walk on a graph is always reversible

For a graph walk: ${\pi }_i{p}_{ij}={\pi }_j{p}_{ji}$ follows from ${\pi }_i/d_i={\pi }_j/d_j$