[Math] For finite Markov Chain, time average distribution is always a stationary distribution

markov chainsstationary-processes

Given some finite state space $\Omega\equiv\{\omega_1,\ldots,\omega_n\}$ be given, and let any Markov chain $\{X_t\}$ with $n\times n$ transition matrix $A$ on $\Omega$ be given. I would like to know if there are standard results out there I can cite that give the following:

  1. There always exists some (not necessarily unique) stationary distribution $\pi$ such that $A\pi = \pi$.
  2. Let any initial distribution $\pi^0\equiv (\pi^0_1,\ldots,\pi^0_n)$ (where $\pi^0_i$ is the initial probability of being in state $\omega_i$) be given, and define $\pi^{t}=\pi^0 A^t$. The "time average limiting distribution" $x$ (is there a more standard term for this out there?) exists: $$x_i \equiv \lim_{t\to\infty}\frac{1}{t} \sum_{s=0}^{t-1} \pi^t_i.$$
  3. The time average limiting distribution $x$ given above is stationary: $x = xA$.

I know this is all implied by the Ergodic Theorem for irreducible Markov chains, but I would like to see that it is also true for all (finite) Markov chains. I don't need convergence to a unique stationary distribution, which is the concern of most of the stuff out there.

Best Answer

All of your statements are true. For the first, you can use a purely linear algebraic fact, that a stochastic matrix always has an eigenvalue of 1 with a left eigenvector whose entries are nonnegative.

For the second, let's say the chain has $m$ communicating classes $C_j$. If the initial condition is entirely in a single communicating class $C_j$ (i.e. $\sum_{i \in C_j} \pi^0_i = 1$), then the time average of the distributions converge to the unique stationary distribution of the Markov chain restricted to $C_j$. This follows from the ergodic theorem. So if you find the time average limit of each subchain, then you can manage the whole chain by writing

$$\mathbb{P} \left ( X_k = i \right ) = \sum_{j=1}^m \mathbb{P} \left ( \left. X_k = i \right | X_0 \in C_{j} \right ) \mathbb{P} \left ( X_0 \in C_{j} \right ) \\ = \mathbb{P} \left ( \left. X_k = i \right | X_0 \in C_{j(i)} \right ) \mathbb{P} \left ( X_0 \in C_{j(i)} \right )$$

where $C_{j(i)}$ is the communicating class of state $i$. Then the second term is constant and the time average of the first term is convergent, so the time average of the whole thing is also convergent.

For the third, you can use linearity:

$$\left ( \frac{\sum_{k=1}^t \pi^k}{t} \right ) A = \frac{\sum_{k=1}^t \pi^k A}{t} = \frac{\left ( \sum_{k=1}^t \pi^k \right ) + \pi^{t+1} - \pi^1}{t}.$$

Taking $t \to \infty$ and exploiting continuity of $A$, we get

$$\left ( \lim_{t \to \infty} \frac{\sum_{k=1}^t \pi^k}{t} \right ) A = \lim_{t \to \infty} \frac{\sum_{k=1}^t \pi^k}{t}.$$

Related Question