Markov Chains: The Stationary Distribution
Definition 1. We say distribution $\pi$ is stationary for the Markov chain $X$ if $\pi P = \pi$. That is if $X_0 \sim \pi$ then $X_n \sim \pi$ for all $n \in \N$.
Remark 2. We will shortly see $\pi(x)$ is the average time the Markov chain spends at location $x$. Points where $\pi(x)$ is higher are visited (proportionally) more often by $X$ than points where $\pi(x)$ is lower. More precisely, when the chain is stationary and aperiodic, we must have \begin{equation}\label{e:piErgodic}\tag{E} \pi(x) = \lim_{N \to \infty} \frac{1}{N} \sum_{n = 0}^{N-1} \one_{\set{X_n = x}} \quad\text{almost surely} \end{equation}
Remark 3. Note a stationary distribution is a left eigenvector of the matrix $P$ with eigenvalue $1$. However, not any left eigenvector with eigenvalue $1$ is a stationary distribution, as such eigenvectors may not be probability distributions.
Uniqueness
Remark 4. In general, the stationary distribution need not be unique. For example $\mathcal X = \set{0, 1}$, and $P = I$ has infinitely many stationary distributions. The gamblers chain (nearest neighbor random walk on $\set{0, \dots, N}$ which is absorbed at the end points) is also not irreducible.
Definition 5. A Markov chain is called irreducible if for any $x, y \in \mathcal X$ there exists a time $n \in \N$ such that $P^n(x, y) > 0$.
If $P$ is irreducible, the stationary distribution is unique.
Lemma 7. If $P$ is irreducible, and $\pi$ is a stationary distribution, then $\pi(x) > 0$ for all $x \in \mathcal X$.
Proof of Theorem 6 . If $\pi_1$ and $\pi_2$ are two stationary distributions, choose $x_0$ that minimizes $\pi_1(x) / \pi_2(x)$. Clearly \begin{equation} \pi_1(x_0) = \sum_{x \in \mathcal X} \frac{\pi_1(x)}{\pi_2(x)} \pi_2(x) P(x, x_0) \geq \sum_{x \in \mathcal X} \frac{\pi_1(x_0)}{\pi_2(x_0)} \pi_2(x) P(x, x_0) % \geq \frac{\pi_1(x_0)}{\pi_2(x_0)} \pi_2(x_0) = \pi_1(x_0)\,. \end{equation} This implies \begin{equation} \sum_{x \in \mathcal X} \frac{\pi_1(x)}{\pi_2(x)} \pi_2(x) P(x, x_0) = \sum_{x \in \mathcal X} \frac{\pi_1(x_0)}{\pi_2(x_0)} \pi_2(x) P(x, x_0) \,. \end{equation} Since $\pi_1(x) / \pi_2(x) \geq \pi_1(x_0) / \pi_2(x_0)$ for all $x$, the above equality can only hold if \begin{equation} \frac{\pi_1(x)}{\pi_2(x)} = \frac{\pi_1(x_0)}{\pi_2(x_0)} \quad\text{for every } x \in \mathcal X \text{ such that } P(x, x_0) > 0\,. \end{equation} for all $x$ such that $P(x, x_0) > 0$. Now for any given $x \in \mathcal X$, irreducibility implies we can find $N = N(x) \in \N$ such that $P^N( x, x_0) > 0$. Since $\pi_1$ and $\pi_2$ are also stationary for $P^N$ the above argument will imply \begin{equation} \frac{\pi_1(x)}{\pi_2(x)} = \frac{\pi_1(x_0)}{\pi_2(x_0)} \quad\text{for every } x \in \mathcal X\,. \end{equation} Since $\sum_{x \in \mathcal X} \pi_1(x) = \sum_{x \in \mathcal X} \pi_2(x) = 1$, this implies $\pi_1 = \pi_2$, finishing the proof.
Existence
If $\abs{\mathcal X} < \infty$, then any Markov chain has a stationary distribution.
To prove this first fix some arbitrary point $a \in \mathcal X$, and define \begin{equation} \tau^{+} = \min \set{ n \geq 1 \st X_n = a } \,. \end{equation} As before $\tau^{+}$ is a stopping time. That is, for every $n \in \N$, the event $\set{\tau^{+} = n}$ can be described using only the random variables $X_0$, …, $X_n$, without involving $X_{n+1}$, $X_{n+2}$, etc.
Lemma 9. For every $y \in \mathcal X$ define \begin{equation} \tilde \pi(y) \defeq \sum_{n \geq 0} \P^a( X_n = y, ~ \tau^{+} > n ) \,. \end{equation} If $\P^a( \tau^{+} < \infty) = 1$, then for every $y \in \mathcal X$ we have \begin{equation} \sum_{x \in \mathcal X} \tilde \pi(x) P(x, y) = \tilde \pi(y) \,. \end{equation}
Proof: Notice $\set{\tau^{+} > n} = \set{X_1 \neq a, X_2 \neq a, \dots, X_n \neq a}$. Using Markov property this implies \begin{align} \P^a( X_{n+1} = y, \tau^{+} > n ) &= \sum_{x \in \mathcal X} \P^a( X_{n+1} = y \given X_n = x, \tau^{+} > n ) \P^a( X_n = x, \tau^{+} > n ) \\ &= \sum_{x \in \mathcal X} P(x, y) \P^a( X_n = x, \tau^{+} > n ) \,. \end{align} Summing in $n$ gives \begin{align} \sum_{x \in \mathcal X} \tilde \pi(x) P(x, y) &= \sum_{n = 1}^\infty \P^a( X_n = y, \tau^{+} \geq n) \\ &= \tilde \pi(y) + \sum_{n=1}^\infty \P^a( X_n = y, \tau^{+} = n) - \P^a(X_0 = y, \tau^{+} > 0) = \tilde \pi(y) \,. \end{align} The last equality is true because if $y \neq a$ then the last two terms on the right are both $0$. If $y = a$, then both these terms are equal.
Lemma 10. If $\abs{\mathcal X} < \infty$ and $(X_n)$ is irreducible, then for every $x \in \mathcal X$, $\sum_{n \geq 0} \P^x( \tau^{+} > n ) < \infty$.
Remark 11. Note $\sum_{n \geq 0} \P^x( \tau^{+} > n ) = \E^x \tau^{+}$.
Outline of the proof of Lemma 10 : By irreducibility, for every $x \in \mathcal X$, there exists $N_x$ such that $P^{N_x}(x, a) > 0$. Let $N = \max N_x$ and $\epsilon = \min_x \P^{N_x}(x, a) > 0$. You should check that this implies \begin{equation} \P^x( \tau^{+} \leq N + 1 ) \geq \epsilon \,, \end{equation} for every $x \in \mathcal X$. Next, note \begin{align} \P^x( \tau^{+} > 2(N+1) ) &= \P^x( \tau^{+} > 2(N+1) \given \tau^{+} > N + 1) \P^a( \tau^{+} > N+1 ) \\ &\leq (1 - \epsilon) \sum_{y \in \mathcal X} \P^x( \tau^{+} > 2(N+1) \given X_{N+1} = y, \tau^{+} > N + 1) P^{N+1}(x, y) \,, \end{align} and show this is at most $(1 - \epsilon)^2$. Use induction to conclude $\P^x( \tau^{+} \geq k(N + 1) ) \leq (1 - \epsilon)^k$, and use this to finish the proof.
Proof of Theorem 8 : Notice $\sum_{y \in \mathcal X} \tilde \pi(y) = \E^a \tau^{+}$. Thus if $(X_n)$ is irreducible, then \begin{equation} \pi(x) \defeq \frac{\tilde \pi(x)}{\E^a \tau^{+}} \end{equation} is the desired stationary distribution.
If $(X_n)$ is not irreducible, then we find a subset $\mathcal X’ \subseteq \mathcal X$ on which $(X_n)$ is an irreducible Markov chain. (This can be done by choosing an essential communicating class, and is described in Section 1.7 of LP17.) Now the above argument ensures the existence of a stationary distribution on $\mathcal X’$. Extending this as $0$ to all of $\mathcal X$ gives the desired stationary distribution.
Corollary 12. If $(X_n)$ is irreducible, then the unique stationary distribution on $\mathcal X$ satisfies \begin{equation} \pi(x) = \frac{1}{\E^x \tau^{+}_x} \quad \text{where}\quad \tau^{+}_x = \min \set{n > 0 \st X_n = x } \,. \end{equation}
Remark 13. When $\mathcal X$ is finite, one can alternately prove this using the Frobenius theorem from linear algebra.
Convergence
We mentioned earlier that the fraction of time a Markov chain spends at a node is proportional to the stationary distribution. While we are not yet in a position to prove that, we can prove the expected fraction of time a Markov chain spends at nodes converges to the stationary distribution. Explicitly, we will show \begin{equation}\label{e:piErgodic2}\tag{E´} \pi(x) = \lim_{N \to \infty} \E \frac{1}{N} \sum_{n = 0}^{N-1} \one_{\set{X_n = x}} = \lim_{N \to \infty} \frac{1}{N} \sum_{n = 0}^{N-1} \P( X_n = x ) \,. \end{equation} (It is useful to compare this to \eqref{e:piErgodic}.) In fact, for \eqref{e:piErgodic2}, we will show that for every $x \in \mathcal X$ we have $\pi(x) = \lim \P( X_n = x)$, without needing to average in $n$ (this is a stronger statement). This convergence, however, doesn’t always hold and we need our Markov chain to satisfy certain conditions.
First off, convergence doesn’t always hold, and the limit may depend on the initial distribution.
Example 14. Let $X_n$ be the simple random walk on $\set{0, \dots, N}$ which is absorbed at the end points $0$ and $N$. $\lim_{n \to \infty} \P(X_n = x)$ exists, but depends on the initial distribution. Specifically,
Example 15. Irreducibility alone doesn’t guarantee convergence to the stationary distribution. For example the chain with transitions $P(0, 1) = P(1, 0) = 1$ and $P(1, 1) = P(0, 0) = 0$ is irreducible, but the distribution need not converge to the stationary distribution.
If, however, the Markov chain is irreducible and aperiodic (defined below), then $\dist(X_n) \to \pi$ no matter what distribution $X_0$ followed.
Definition 16. A Markov chain is called aperiodic if for all $x \in \mathcal X$, \begin{equation} \gcd\set{n \geq 1 \st P^n(x, x) > 0} = 1\,. \end{equation}
Example 17. The simple random walk is irreducible, but not aperiodic. If instead $\xi_n$ are i.i.d. random variables such that $\P(\xi_n = 0) = 1/2$ and $\P(\xi_n = \pm 1) = 1/4$, then the lazy random walk defined by $X_{n+1} = X_n + \xi_{n+1}$ is irreducible and aperiodic.
Example 18. The Markov chain with $P=I$ is aperiodic but not irreducible (if $\abs{\mathcal X} > 1$).
Remark 19. If a Markov chain is irreducible but not aperiodic, one common trick is to introduce lazyness: Flip an independent fair coin. If it lands heads, don’t move. If it lands tails, move according to the original transition kernel. That is, define a new transition matrix $Q$ by \begin{equation} Q(x,y) = \frac{1}{2} (I + P) = \begin{cases} \frac{1}{2}(1 + P(x, x)) & y = x\,,\\ \frac{1}{2} P(x, y) & y \neq x \,. \end{cases} \end{equation} The new chain will be both irreducible and aperiodic, and have the same stationary distribution.
Definition 20. For any two probability distributions $\mu, \nu$ we define the total variation distance between $\mu$ and $\nu$ by \begin{equation} \norm{\mu - \nu}_\TV \defeq \frac{1}{2} \sum_{x \in \mathcal X} \abs{\mu(x) - \nu(x) } \,. \end{equation}
Definition 21. We say $\dist(X_n) \to \pi$ in total variation as $n \to \infty$, if we have $\norm{\dist(X_n) - \pi}_\TV = 0$ as $n \to \infty$.
If a Markov chain is irreducible and aperiodic, then $\dist(X_n) \to \pi$ in total variation as $n \to \infty$.
Remark 23. Notice $\norm{\dist(X_n) - \pi}_\TV = 0$ as $n \to \infty$ is equivalent to having \begin{equation} \lim_{n \to \infty} \frac{1}{2} \sum_{x \in \mathcal X} \abs{ \P( X_n = x ) - \pi(x) } = 0\,. \end{equation}
Lemma 24. If a Markov chain is aperiodic, then there exists $N \in \N$ such that $P^n(x, x) > 0$ for all $x \in \mathcal X$ and $n \geq N$.
Proof: This follows quickly from the fact that if $S \subseteq \N$ is non-empty and $\gcd(S) = 1$, then there exists $N \in \N$ such that for every $n \geq N$ there exists $k \in \N$, $s_1, \dots, s_k \in S$ and $m_1, \dots, m_k \in \N$ such that $n = \sum_{i=1}^k m_i s_i$.
Lemma 25. If a Markov chain is irreducible and aperiodic, there exists $N \in \N$ such that $P^N(x, y) > 0$ for all $x, y \in \mathcal X$.
Lemma 26. Let $Q$ be the transition kernel of a Markov chain If $\mu, \mu$ and $\nu$ are any two probability distributions, then \begin{equation} \norm{\mu Q - \nu Q}_\TV \norm{(\mu - \nu) Q}_\TV \leq \norm{\mu - \nu}_\TV \,. \end{equation}
Suppose there exists a probability distribution $\gamma$, and a number $\delta > 0$ are such that $Q(x, y) \geq \delta \gamma(y)$. \begin{equation} \norm{\mu Q - \nu Q}_\TV \leq (1 - \delta) \norm{\mu - \nu}_\TV \end{equation}
Proof: Write $Q(x, y) = \delta \gamma(y) + (1 - \delta) Q_2(x, y)$ for some stochastic matrix $Q_2$, and use the previous lemma.
Proof of Theorem 22 . Choose $N$ as in Lemma 25 , $\delta = \abs{\mathcal X} \min P^N(x, y)$, and $\gamma(y) = 1 / \abs{\mathcal X}$. Now use Lemma 26 and Lemma 27 to show \begin{equation} \norm{\dist( X_{k N + j} ) - \pi}_\TV \leq (1 - \delta)^k \,. \end{equation}
Remark 28. The above proof combined with the contraction mapping principle can be used to given an alternate proof of existence of a stationary distribution.