Let \(X_0, X_1, ...\) denote a Markov chain such that (1) the state space is finite and (2) the chain is irreducible (can get from any state to any other state - not necessarily in a single step!) and aperiodic (can only return to a state in multiples of \(d\) steps).
Then there exists a unique stationary distribution \(pi\) such that:
\(\forall i \neq j\), $$\lim_{t \rightarrow \infty} \mathbb{P}[X_t = i | X_0 = j] = \pi_j$$ |
\(\forall i\), $$\pi_i = 1/\mathbb{E}[\min_{t > 0} {t: X_t = i | X_0 = i }]$$ |
What happens if the Markov chain has an infinite state space? Then either a stationary distribution exists, or the probability of going from \(X_0=j\) to \(X_t = i\) is \(0\).
What happens if the Markov chain is not irreducible? Then we can decompose the graph into irreducible subcomponents, and the chain will convert to one of those subcomponents, but which one depends on the initial conditions.
What happens if the Markov chain is periodic? There is still a unique stationary distribution, but we can no longer guarantee that \(\forall i \neq j\), \(\lim_{t \rightarrow \infty} \mathbb{P}[X_t = i | X_0 = j] = \pi_j\). To understand why, imagine a deterministic loop for the state space. The minimum time to return is also deterministic (the length of the loop \(\lvert S \lvert\)), so the probability of being in state \(i\) depends on the number of steps taken.
Suppose \(X_0, X_1, ...\) is an irreducible, aperiodic Markov chain in a finite state space. If the transition matrix \(P\) is symmetric, then the unique stationary distribution is uniform.
Proof: Let \(\pi_i = \frac{1}{\lvert S \lvert}\). Then \(\pi_i = \sum_j P_{ij} \pi_j = \frac{1}{\lvert S \lvert} \sum_i P_{ij} = \frac{1}{\lvert S \lvert}\)
Example: Take a deck of cards, choose 2 cards independently, then swap them. This is an aperiodic, irreducible Markov chain with finite state space. By the previous proposition, the unique stationary distribution is uniform, meaning the deck will be equally mixed.
Let \(X_0, X_1, ...\) be a random walk on a connected, undirected, non-bipartite graph. Then there exists a unique stationary distribution \(\pi\) such that \(\forall v \ in \mathcal{V}\), \(\pi_v = \frac{deg(v)}{2 \lvert E \lvert}\).