The Markov Chain Ergodic Theorem

Long-Run Frequencies Along a Path

A Markov chain’s distribution at a fixed time and the frequencies observed along one long trajectory describe different kinds of behavior. A periodic chain may keep switching its one-time distribution, even though the fraction of time spent in each state settles down. The Markov chain ergodic theorem gives a precise statement about these pathwise frequencies: for an irreducible positive recurrent chain, the long-run fraction of visits to a state is its stationary probability, almost surely.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\). For a state \(j\) and an integer \(N\ge1\), define its empirical frequency through time \(N-1\) by \[ \widehat{\pi}_N(j)=\frac{1}{N}\sum_{n=0}^{N-1}\mathbf{1}_{\{X_n=j\}}. \] This counts visits at times \(0,\ldots,N-1\), including the initial state when \(X_0=j\). A stationary distribution is a probability row vector \(\pi\) satisfying \(\pi P=\pi\).

For countable irreducible chains, a standard recurrence theorem states that positive recurrence is equivalent to existence of a stationary probability distribution, and that this distribution is unique. We use this standard result here. The theorem below concerns the almost-sure limit of \(\widehat{\pi}_N(j)\), not convergence of the distributions of \(X_n\).

Why the Theorem Applies From Any Initial State

The central ergodic result used to obtain this theorem is the standard Birkhoff ergodic theorem: for a stationary ergodic process, time averages of an integrable function converge almost surely to its expectation. We do not prove Birkhoff’s theorem here. Another standard fact is that the stationary path process of an irreducible positive recurrent Markov chain is ergodic under time shift; this fact does not require aperiodicity. Applied with the bounded function \(\mathbf{1}_{\{X_0=j\}}\), Birkhoff’s theorem gives the claimed limit when the chain starts with distribution \(\pi\).

To pass from stationary initialization to a fixed initial state \(i\), choose a reference state \(r\). An irreducible positive recurrent chain hits \(r\) almost surely from every initial state; this is a standard recurrence fact. Let \(\tau=\inf\{n\ge0:X_n=r\}\). By the Markov property at this hitting time, the path from time \(\tau\) onward has the law of the chain started at \(r\). Thus the stationary-initialized result also gives the empirical-frequency limit under \(\mathbb{P}_r\): the same conclusion holds under any fixed start, since this is the stationary result transferred to \(r\) by the standard stationary Markov-chain ergodic theorem and recurrence. More directly, the standard ergodic theorem for an irreducible positive recurrent chain applies from \(r\). For any fixed \(i\), the initial segment before \(\tau\) has finite length almost surely, and for each \(N>\tau\), \[ \left|\widehat{\pi}_N(j)-\frac{1}{N}\sum_{n=\tau}^{N-1}\mathbf{1}_{\{X_n=j\}}\right| \le \frac{\tau}{N}. \] The right-hand side tends to zero almost surely. The post-\(\tau\) average has the same limit as the average from \(r\), because changing its time index by the finite amount \(\tau\) changes the numerator by at most \(\tau\). This proves the theorem for every fixed \(i\).

For a random initial state with any probability distribution \(\mu\), the event of failure has probability \(\sum_{i\in S}\mu_i\,\mathbb{P}_i(\text{failure})=0\). Finally, since \(S\) is countable, the intersection over all \(j\in S\) of the probability-one events for individual states still has probability one. This establishes the simultaneous statement.

The theorem’s proof relies on standard ergodic and recurrence results, rather than deriving them here. Its practical content is especially simple: changing the initial state can affect a finite initial portion of a trajectory, but it cannot change the limiting fraction of time spent in any state.

Worked Applications

Consequences and Common Misreadings

Proof. Let \(\pi\) be the stationary distribution given by the recurrence theorem, and suppose \(\nu\) is any other stationary probability distribution. Start the chain with distribution \(\nu\). By the ergodic theorem, \(\widehat{\pi}_N(j)\to\pi_j\) almost surely for each \(j\). Since \(0\le\widehat{\pi}_N(j)\le1\), bounded convergence gives \(\mathbb{E}_{\nu}[\widehat{\pi}_N(j)]\to\pi_j\). But stationarity under \(\nu\) gives, for every \(N\), \[ \mathbb{E}_{\nu}[\widehat{\pi}_N(j)] =\frac1N\sum_{n=0}^{N-1}\mathbb{P}_{\nu}(X_n=j) =\frac1N\sum_{n=0}^{N-1}\nu_j =\nu_j. \] Therefore \(\nu_j=\pi_j\) for each \(j\), so \(\nu=\pi\). \(\square\)

A common mistake is to infer that empirical frequencies fail to converge whenever the one-time distribution fails to converge. In the alternating-chain example, starting at \(0\), \(\mathbb{P}_0(X_n=0)\) equals \(1\) for even \(n\) and \(0\) for odd \(n\), so it has no limit. But the empirical frequency is \(\lceil N/2\rceil/N\), which tends to \(\tfrac12\). The theorem concerns averages along a path, not the distribution at an individual time.

Another mistake is to impose aperiodicity as a hypothesis. Aperiodicity is important for many results about convergence of the distributions \(\mu P^n\) to \(\pi\). It is not needed for the empirical-frequency limit. Conversely, the ergodic theorem does not itself say that \(\mu P^n\to\pi\); a stationary distribution describes both results, but the modes of convergence differ.

The assumptions also matter. Irreducibility prevents the chain from having separate classes with different long-run frequencies. Positive recurrence ensures a stationary probability distribution and finite mean return times. Without these conditions, the stated conclusion need not hold. For instance, a chain with two absorbing states is not irreducible: if it starts at state \(0\), its frequency of state \(0\) is \(1\), while if it starts at state \(1\), that frequency is \(0\). There is no single stationary distribution that gives the long-run frequency from both initial states.