06. Markov Chain - Stationary Distributions, Convergence to Equilibrium, and Time-Reversal

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$

Link to original

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$$

Link to original

---

6.1 Stationary Distributions and Convergence to Equilibrium: Main Theorems

Existence and Uniqueness of Stationary Distributions

Let $P$ be an irreducible transition matrix then

1. $P$ has stationary distribution if and only if $P$ is positive recurrent

2. If $P$ has a stationary distribution but it is unique and given by

$${\pi }_i=\frac{1}{m_i}\text{ for all }i$$

where $m_i$ is the mean return time to state $i$

Link to original

Convergence to Equilibrium

Let $P$ be a transition matrix that is irreducible and aperiodic with stationary distribution $\pi$
Let $X_n$ be a Markov Chain with transition matrix $P$ and any distribution then

$$P(X_n=j)\to {\pi }_j\text{ as }n\to \infty \text{ for all }j\in I$$

In particular then

$$p_{ij}^{(n)}\to {\pi }_j\text{ as }n\to \infty \text{ for all }i,j\in I$$

Link to original

Ergodic Theorem

Let $P$ be a irreducible transition matrix
Let $V_i(n)$ be the number of visits to state $i$ before time $n$ so

$$V_i(n)=\sum _{r=0}^{n-1}1(X_r=i)$$

Then for any initial distribution

$$\frac{V_i(n)}{n}\to \frac{1}{m_i}\text{ almost surely as }n\to \infty \text{ for all }i\in I$$

So

$$\mathbb{P}\left(\frac{V_i(n)}{n}\to \frac{1}{m_i}\text{ as }n\to \infty \right)=1$$

Link to original

---

6.2 Examples of Stationary Distributions

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

Link to original

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$$

Link to original

---

6.3 Proof of Theorems in 6.1 (Non-Examinable)

Refer to Lecture Notes - page 57 for proofs

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}$$

Link to original

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}$$

Link to original

---

6.4 Time-Reversal

Time-Reversal of a Markov Chain

Let $P$ be an irreducible transition matrix with stationary distribution $\pi$
Let $(X_0,X_1,\cdots ,X_N)$ be $\mathrm{Markov}(\pi ,P)$

For $0\le n\le N$ define

$$Y_n=X_{N-n}$$

Then

$$(Y_0,Y_1,\cdots ,Y_N)\text{ is }\mathrm{Markov}(\pi ,Q)$$

where transition matrix $Q=(q_{ij})$ is defined by

$$q_{ij}=\frac{{\pi }_j}{{\pi }_i}{p}_{ij}$$

and matrix $Q$ has stationary distribution $\pi$

Note that chain $Y$ is called the time-reversal of chain $X$

Proof

As

$$\sum _j{q}_{ij}=\frac{1}{{\pi }_i}\sum _j{\pi }_j{p}_{ji}=\frac{1}{{\pi }_i}{\pi }_i=1$$

Then $Q$ is a stochastic matrix

As $\pi$ is stationary for $P$ then

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

So $\pi$ is stationary for $Q$

Consider sequence of states $i_0,i_1,\cdots ,i_N$ then

$$\begin{array}{rl}\mathbb{P}(Y_0=i_0,& Y_1=i_1,\cdots ,Y_N=i_N)\\ & =\mathbb{P}(X_0=i_N,X_1=i_{N-1},\cdots ,X_N=i_0)\\ & ={\pi }_{i_N}{p}_{i_N{i}_{N-1}}{p}_{i_{N-1}{i}_{N-2}}\cdots p_{i_2{i}_1}{p}_{i_1{i}_0}\\ & ={\pi }_{i_N}\left(q_{i_{N-1}{i}_N}\frac{{\pi }_{i_{N-1}}}{{\pi }_{i_N}}\right)\left(q_{i_{N-2}{i}_{N-1}}\frac{{\pi }_{i_{N-2}}}{{\pi }_{i_{N-1}}}\right)\cdots \left(q_{i_1{i}_2}\frac{{\pi }_{i_1}}{{\pi }_{i_2}}\right)\left(q_{i_0{i}_1}\frac{{\pi }_{i_0}}{{\pi }_{i_1}}\right)\\ & ={\pi }_{i_0}{q}_{i_0{i}_1}{q}_{i_1{i}_2}\cdots q_{i_{N-2}{i}_{N-1}}{q}_{i_{N-1}{i}_N}\end{array}$$

Hence

$$Y\sim \mathrm{Markov}(\pi ,Q)$$

Link to original

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$$

Link to original

Detailed Balance Equations

Let $P$ be an irreducible transition matrix with stationary distribution $\pi$

$P$ is reversible if and only if

$${\pi }_i{p}_{ij}={\pi }_j{p}_{ji}\text{ for all }i,j$$

Link to original

Detailed Balance Implies Stationary

Let $P$ be a transition matrix with distribution $\pi$ then

If $P$ and $\pi$ are in detailed balance then

$$\pi \text{ is stationary for }P$$

Proof

For any $j$ then

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

Link to original

---

6.4.1 Examples

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$

Link to original