A Regenerative Proof of the Ergodic Theorem

Why Return Cycles Give Long-Run Frequencies

A Markov chain’s successive steps are dependent, so the usual strong law for independent observations cannot be applied directly to its state indicators. At returns to a fixed state, however, the future starts afresh: the path segments between consecutive returns are independent and have the same distribution. The state frequency can therefore be obtained by applying the strong law to the number of visits in a cycle and the length of that cycle.

Let \((X_n)_{n\ge 0}\) be a Markov chain on a countable state space \(S\), defined on a probability space \((\Omega,\mathcal F,\mathbb P)\), with transition matrix \(P=(p_{ij})\). Use the filtration \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\). The matrix is row-stochastic: \(\sum_{j\in S}p_{ij}=1\) for every \(i\). The chain is irreducible if each state can be reached from each other state with positive probability in some finite number of steps. It is positive recurrent if it is irreducible and its expected return time to a state is finite. For an irreducible chain, if this holds for one state, it holds for every state.

The return time is excluded from the cycle: the cycle includes its starting visit to \(a\), but not the next visit to \(a\), which starts the following cycle. In an irreducible positive recurrent chain, the return cycles under \(\mathbb P_a\) are independent and identically distributed by the strong Markov property. Their common length has finite mean \(m_a=\mathbb E_a[T_a^+]\), where \(T_a^+=\inf\{n\ge 1:X_n=a\}\).

The Stationary Distribution from One Cycle

Define the expected number of visits to \(j\) in one cycle by \(c_j=\mathbb E_a[R_1(j)]\). Since \(R_1(j)\le T_a^+\), each \(c_j\) is finite. The expected cycle length is the sum of the expected visit counts across states, because exactly one state is occupied at every time in the cycle.

Proof. Nonnegativity is immediate. Summing the visit counts over the countable state space and using monotone convergence gives \(\sum_{j\in S}c_j=\mathbb E_a[T_a^+]=m_a\). Thus \(\rho\) is a probability distribution. To check invariance, use Tonelli’s theorem and the Markov property. Since \(\{n<T_a^+\}\) is \(\mathcal F_n\)-measurable,

The last sum counts visits to \(j\) at times \(1,\ldots,T_a^+\). Compared with the cycle count at times \(0,\ldots,T_a^+-1\), it removes the term \(\mathbf 1_{\{X_0=j\}}\) and adds \(\mathbf 1_{\{X_{T_a^+}=j\}}\). Both \(X_0\) and \(X_{T_a^+}\) equal \(a\), so these terms are equal and the two counts agree. Hence \(\sum_i c_i p_{ij}=c_j\). Dividing by \(m_a\) proves \(\rho P=\rho\). The standard uniqueness theorem for the stationary distribution of an irreducible chain with a stationary probability distribution then gives \(\rho=\pi\); that uniqueness result is established in the earlier material on stationary distributions. \(\square\)

This cycle formula identifies the target of the frequency limit. The remaining step is to show that observed cycle lengths and visit counts approach their expectations at the appropriate rates.

The Regenerative State-Frequency Theorem

Proof. First start the chain at the regenerative state \(a\). Write \(S_k=T_k\) for the time of the \(k\)th return, with \(S_0=0\), and set \(K(n)=\max\{k:S_k\le n\}\). By the strong law of large numbers applied to the independent, identically distributed cycle lengths and visit counts,

Because \(S_{K(n)}\le n<S_{K(n)+1}\), these limits imply \(K(n)/n\to 1/m_a\). Indeed, \(K(n)\to\infty\), and dividing the two inequalities by \(K(n)\), the lower and upper bounds for \(n/K(n)\) both tend to \(m_a\).

The time indices from \(0\) through \(n-1\) contain all the first \(K(n)\) complete cycles and a possibly incomplete part of the next cycle. That partial cycle contributes at most \(L_{K(n)+1}\) visits to any state. We verify that this remainder is negligible. From \(S_k/k\to m_a\) and \(S_{k-1}/(k-1)\to m_a\), it follows that \(L_k/k\to0\), since \(L_k=S_k-S_{k-1}\). Also \((K(n)+1)/n\to1/m_a\), so \(L_{K(n)+1}/n\to0\). Consequently,

where the final equality is the cycle formula proved above. This proves the claim under \(\mathbb P_a\).

Now start at any \(x\in S\). Irreducibility and positive recurrence imply that the hitting time \(H=\inf\{n\ge0:X_n=a\}\) is finite almost surely. The first \(H\) terms of the time average contribute at most \(H/n\), which tends to zero almost surely. By the strong Markov property at \(H\), the path from time \(H\) onward has the law of the chain started at \(a\), so its state frequency converges almost surely to \(\pi_j\). Removing or adding the finite initial segment does not change the limit. The result follows under \(\mathbb P_x\). \(\square\)

The strong law used here requires independent, identically distributed integrable variables. Both requirements have a specific role: the Markov property at return times gives identical, independent cycles, and positive recurrence gives the finite mean cycle length. The visit count is integrable because it is bounded by the cycle length.

Worked Cycle Calculations

What the Result Does—and Does Not—Require

Aperiodicity is not needed for the state-frequency theorem. The deterministic three-state cycle illustrates why: its distribution at a fixed time does not settle to a single distribution, but its long-run fraction of time in each state does converge. Distributional convergence and convergence of time averages are different claims.

Positive recurrence, by contrast, is essential to this finite-mean cycle argument. For example, the simple symmetric random walk on the integers is irreducible and recurrent but null recurrent: its expected return time to \(0\) is infinite, and it has no stationary probability distribution. The proposition’s normalization \(c_j/m_0\) therefore cannot produce a stationary probability distribution. In the regenerative proof, a finite mean cycle length is what lets the strong law convert cycle counts into frequencies per unit time.

Common mistake: counting the return as part of the old cycle. In the deterministic example, the cycle from \(1\) to its next return has \(X_0=1\), \(X_1=2\), \(X_2=3\), and \(X_3=1\). The cycle is the half-open time interval from \(0\) up to, but not including, \(3\). A wrong count that labels the states at indices \(1,2,3\) as \(1,2,3\) misreads the trajectory: the actual states at those indices are \(2,3,1\). The correct cycle visits \(1,2,3\) at indices \(0,1,2\), respectively. Including the endpoint while also starting the next cycle at that same return can double-count its boundary state.