the ergodic theorem for Markov chains

There are two natural ways to ask 'how often is it sunny?'. One is to watch a single long history and count the fraction of days that were sunny — a time average along one path. The other is to look at the equilibrium distribution and read off the stationary probability of sun — a space average over states. The ergodic theorem says these two give the SAME answer: a single long run reveals the equilibrium.

Formally, for an irreducible positive-recurrent chain, the long-run fraction of time spent in state i converges to pi(i), the stationary probability — and more generally the time-average of any function f of the state, (1/n) times the sum of f(X_0) + ... + f(X_(n-1)), converges to its stationary expectation, the sum over states of pi(i) f(i). This holds almost surely, for almost every individual trajectory, not merely on average. One sufficiently long sample path is statistically representative of the whole chain.

This is the law of large numbers for dependent, chain-correlated data, and it is what makes simulation legitimate. You cannot run a chain infinitely many times, but you can run it once for a long time and average — Markov chain Monte Carlo lives entirely on this guarantee: build a chain whose stationary distribution is your target, run it, and time-average to estimate any quantity you want. Beautifully, the ergodic theorem needs only irreducibility and positive recurrence — NOT aperiodicity — so even a periodic chain, which never converges pointwise, still has honest long-run time averages.