Invariant Distribution

• When do they exist?
• When are they unique?

See Definition (Distribution Vector).

Theorem (Distribution of a Markov Chain)

Let $X$ be a Markov Chain. The distribution of $X$ at time $t$ is given by

$${\pi }_t={\pi }_0{P}^t$$

where ${\pi }_t$ is the distribution vector at time $t=0,1,2,\dots$. $P^0$ is the identity matrix.

Proof: Use induction.

Definition (Stationary or Invariant Distribution)

Let $P=[p_{ij}]$ be the transition matrix for the Markov Chain $\{X_n{\}}_{n=0}^{\infty }$ with $S=\{1,2,\dots ,N\}$. A probability vector $\pi \in {\mathbb{R}}^N$ is a stationary or invariant distribution for $X_n$ (or for $P$) if

$$\pi P=\pi$$

Remark (Conclusions from Examples 1,2)

The examples 1 and 2 show that asymptotic distribution of $X_n$ is the invariant distribution.

Definition (Reducible)

If two states $i,j\in S$ are reachable from one another, then we say that can communicate with one another. This communicability forms an equivalence class (proof omitted).

A Markov Chain is reducible if there are two or more communication classes.

Definition (Periodic)

A Markov Chain is periodic if there is a state that is returned at regular intervals greater than $1$ step.

Theorem (Uniqueness of Invariant Distributions)

An invariant distribution for a Markov Chain unique unless the MC is reducible or periodic.

Definition (Regular Transition Matrices)

A finite state time-homogeneous MC $X_n(n\ge 0)$ with transition matrix $P$ is regular if there exists an integer $k\ge 1$ such that $p^k>0$ (i.e. all entries of $P^k$ are strictly positive).

Example 1 (Simple Regularity)

Consider

$$P=\left(\begin{array}{cc}3/4& 1/4\\ 1/6& 5/6\end{array}\right)$$

This MC is regular. Immediately, we see that if $k=1$, the entries are positive.

Theorem (Regular MC Gives Unique Stationary Distributions)

Let $X_n(n\ge 0)$ be a regular $N-$state Markov Chain with transition matrix $P$. Then:

1. The chain $X_n(n\ge 0)$ has a unique stationary distribution $\pi$ with $\pi >0$.
2. The probabilities converge: $$\underset{n\to \infty }{\lim }{P}^n=\left(\begin{array}{c}\pi \\ ⋮\\ \pi \end{array}\right)$$ i.e. ${\lim }_{n\to \infty }{p}_n(i,j)=\pi (j)$ where $j$ represents the row of $P^n$.
3. For any initial distribution ${\pi }_0$, $$\underset{n\to \infty }{\lim }{\pi }_0{P}^n=\pi$$ Or, ${\lim }_{n\to \infty }P(X_n=j)=\pi (j)$ for all states $j$.

Proof:

Let $\pi$ be the limit of the state distribution over time, such that $\pi ={\lim }_{n\to \infty }{\pi }_{n+1}$. Since ${\pi }_{n+1}={\pi }_0{P}^{n+1}$ via Theorem (Distribution of a Markov Chain), then ${\pi }_{n+1}=({\pi }_0{P}^n)\cdot P$. We apply the limit and get

$$\underset{n\to \infty }{\lim }({\pi }_0{P}^n)\cdot P=\pi P$$

and that $\pi$ is a fixed point for $P$. This shows $\pi$ exists and is stationary. By $(2)$, since every row of matrix $P^n$ converges to the same $\pi$, then $\pi$ is unique, thus $(1)$. Then $(2)⟹(3)$ because the row-vector ${\pi }_0=(a_0,a_1,\dots ,a_N)$ has its entries sum to $1$.

So,

$$\underset{n\to \infty }{\lim }{\pi }_0\cdot P^n={\pi }_0\cdot \left(\begin{array}{c}\pi \\ ⋮\\ \pi \end{array}\right)$$

Consider the first component of the resulting vector:

$$(({\pi }_0(0)\cdot \pi (1))+({\pi }_0(1)\cdot \pi (1))+\cdots )$$

We can factor out the stationary probability $\pi (j)$ for each component and get

$$\pi (j)\cdot \sum _i{\pi }_0(i)$$

which is precisely equal to $\pi (j)\cdot 1=\pi (j)$. Thus it is independent.

Solving For Stationary Distributions

How do we find $\pi$? We can either:

1. Solve $\pi P=\pi$ or
2. Diagonalize $P=U\Lambda U^{-1}$.

So,

$$\begin{array}{rl}\underset{n\to \infty }{\lim }{P}^n& =\underset{n\to \infty }{\lim }{\left(U\Lambda U^{-1}\right)}^n\\ & =U\left(\underset{n\to \infty }{\lim }{\Lambda }^n\right)U^{-1}\\ & =\left(\begin{array}{c}\pi \\ ⋮\\ \pi \end{array}\right)\end{array}$$

The last line is from the fact that the stationary matrix is from its eigenvalues. Also recall that diagonalization of a matrix $M$ gives $U$, it’s matrix of eigenvectors and $\Lambda$, a Diagonal matrix of eigenvalues.

Note that ${\lim }_{n\to \infty }{\Lambda }^n$ collapses to

$$\left(\begin{array}{cccc}1& 0& \dots & 0\\ 0& 0& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & 0\end{array}\right)$$

because one eigenvalue of a stochastic matrix will be $1$. The rest are $|\lambda |<1$, and so ${\lambda }^n\to 0$ as $n\to \infty$.

Remark (Stationaries Have Equal Out/Inflow)

For a distribution to be stationary, the total outflow from a state $i$ must be exactly equal to the total inflow into that same state.

$$\sum _j{\pi }_i\cdot p(i,j)=\sum _j{\pi }_j\cdot p(j,i)$$

Definition (Detailed Balance)

A stochastic matrix $P$ and a probability vector $\lambda$ satisfy detailed balance if

$${\lambda }_i\cdot p(i,j)={\lambda }_j\cdot p(j,i)$$

for all $i,j\in S$.

Proposition (Detailed Balance is Stationary)

If a stochastic matrix $P$ and a probability vector $\lambda$ satisfy detailed balance then $\lambda P=\lambda$, i.e. $\lambda$ is stationary with respect to $P$.

Proof:

$$(\lambda P{)}_j=\sum _i{\lambda }_i\cdot p(i,j)=\sum _i{\lambda }_{j}p(j,i)={\lambda }_j$$

for row $j$.

Fundamental Theorem of Markov Chains

If a Markov Chain is a irreducible and aperiodic and has a stationary distribution $\pi$, then

1. $\pi$ is the unique stationary distribution
2. The distribution of the state at time $n$ converges to $\pi$ as $n\to \infty$ regardless of the initial distribution ${\pi }_0$, or that $$\underset{n\to \infty }{\lim }{\pi }_0{P}^n=\pi$$

Remark on Regularity: This theorem is the functional equivalent of the Regular MC Theorem. In finite state spaces, the conditions (irreducible + aperiodic) are exactly what define a regular transition matrix ($P^k>0$ for some $k$).

Proof: See Theorem (Regular MC Gives Unique Stationary Distributions).