The Ergodic Theorem for Markov Chains

Proof technique: renewal-reward theory applied to excursions between visits to a fixed reference state, combined with the classical Strong Law of Large Numbers (SLLN). Fix a reference state $i \in S$. By irreducibility, from any starting distribution the chain reaches $i$ in finite time almost surely (standard fact for irreducible countable chains: since $i$ communicates with every state, and the state space is countable, the chain visits $i$ eventually with probability 1 — this uses only irreducibility and does not require positive recurrence). So without loss of generality we may assume the chain starts at $X_0 = i$; the finitely many initial steps before the first visit to $i$ do not affect any of the a.s. limits below, since dividing by $n \to \infty$ washes out any fixed finite prefix.

Step 1: Construct i.i.d. excursions. Define the successive return times to $i$:

By recurrence of $i$ (which holds since the chain is positive recurrent, a fortiori recurrent), each $T_i^{(r)}$ is finite almost surely, and the chain returns to $i$ infinitely often a.s. Define the $r$-th excursion as the block of random variables

and its length $L_r = T_i^{(r)} - T_i^{(r-1)}$. By the strong Markov property applied at the stopping times $T_i^{(r)}$ (each of which is a stopping time since the event $\{T_i^{(r)} = n\}$ depends only on $X_0, \dots, X_n$), the process after time $T_i^{(r-1)}$, started at $X_{T_i^{(r-1)}} = i$, is a probabilistic copy of the whole chain started afresh at $i$, independent of everything that happened before time $T_i^{(r-1)}$. Consequently the excursions $E_1, E_2, \dots$ are i.i.d. random elements (as sequences), and in particular the lengths $L_1, L_2, \dots$ are i.i.d. with

By positive recurrence, $m_i < \infty$.

Step 2: Reward structure for visits to a state $j$. For each excursion $E_r$, define the "reward"

the number of visits to $j$ strictly within the $r$-th excursion (using the half-open convention so successive excursions partition the time axis without double-counting the shared endpoint $i$). Since $E_1, E_2, \dots$ are i.i.d., so are $R_1(j), R_2(j), \dots$, with common mean

finite because $R_r(j) \le L_r$ and $\mathbb{E}[L_r] = m_i < \infty$ (a nonnegative random variable bounded above in expectation by a finite number has finite expectation).

Step 3: Apply the SLLN to excursion lengths and rewards. Since $L_1, L_2, \ldots$ are i.i.d. with finite mean $m_i$, the classical Kolmogorov Strong Law of Large Numbers gives

Note $\sum_{s=1}^r L_s = T_i^{(r)}$, the time of the $r$-th return. So

Similarly, since $R_1(j), R_2(j), \dots$ are i.i.d. with finite mean $\gamma_i(j)$, the SLLN gives

Note that $\sum_{s=1}^r R_s(j)$ counts the number of visits to $j$ up to time $T_i^{(r)}$, i.e. $\sum_{s=1}^r R_s(j) = V_j(T_i^{(r)})$.

Step 4: Sandwich to convert renewal-indexed convergence to time-indexed convergence. Because the chain visits $i$ infinitely often a.s., for every $n$ there is (a.s., for $n$ large) a unique $r = r(n)$ with $T_i^{(r)} \le n < T_i^{(r+1)}$, and $r(n) \to \infty$ as $n \to \infty$. Since $V_j(\cdot)$ is nondecreasing,

Divide through by $n$ and use $T_i^{(r(n))} \le n < T_i^{(r(n)+1)}$:

Write the left side as

more directly: using $(\ast)$ and $(\ast\ast)$ along the (a.s. infinite) subsequence $r(n) \to \infty$,

all almost surely (as $r(n)\to\infty$ a.s.). Multiplying/dividing these a.s. limits (all nondegenerate, positive, finite constants) shows both the lower and upper bounds on $V_j(n)/n$ converge to the same limit

By the squeeze theorem, almost surely,

Step 5: Identify the limit with $\pi(j)$. Set $\pi(j) := \gamma_i(j)/m_i$ for each $j$. First check $\pi$ is a probability distribution: summing $\gamma_i(j)$ over $j \in S$ counts every one of the $T_i$ steps of a single excursion exactly once (since every visited state $X_k$, $0 \le k < T_i$, is some state $j$), so

Also $\pi(j) \ge 0$ for all $j$. Taking $j = i$: every excursion visits $i$ exactly once in $[T_i^{(r-1)}, T_i^{(r)})$ (at its start), so $\gamma_i(i) = 1$ and $\pi(i) = 1/m_i$, matching the claimed formula $\pi(j) = 1/m_j$ at $j = i$; since $i$ was an arbitrary state, this gives $\pi(j) = 1/m_j$ for every $j$ (applying the whole argument with reference state $j$ in place of $i$ and reading off $\pi(j) = 1/m_j$ directly, or by the stationarity argument below combined with uniqueness). Next, show $\pi$ is stationary, i.e., $\pi P = \pi$. This is the standard renewal/occupation-measure computation: consider $\sum_l \gamma_i(l) p_{lj}$. By definition,

so, using the Markov property to write $\Pr_i(X_k = l, X_{k+1}=j, k < T_i) = \Pr_i(X_k=l,k<T_i)\,p_{lj}$ (valid because $\{k < T_i\}$ is determined by $X_0,\dots,X_k$, so conditioning on $X_k = l$ and $k < T_i$, the next step's transition still uses row $l$ of $P$),

For $j \ne i$: the events $\{X_k=j,\,k\le T_i\}$ for $k\ge1$ equal $\{X_k=j,\,k<T_i\}$ (since $X_{T_i}=i\neq j$), so the sum equals $\gamma_i(j)$ exactly by definition (re-indexing $k \ge 1$ vs. $k\ge0$ costs nothing since the $k=0$ term $\Pr_i(X_0=j)=0$ as $X_0=i\ne j$). For $j = i$: the sum is $\sum_{k\ge1}\Pr_i(X_k=i,\,k\le T_i) = \Pr_i(X_{T_i}=i) = 1= \gamma_i(i)$ (the only $k\le T_i$ with $X_k=i$ and $k\ge1$ is $k=T_i$, by definition of $T_i$ as the first return). In both cases,

Dividing by $m_i$ gives $\sum_l \pi(l) p_{lj} = \pi(j)$ for all $j$, i.e. $\pi P = \pi$: $\pi$ is stationary.

Step 6: Uniqueness of the stationary distribution. Suppose $\nu$ is any stationary distribution. By induction, $\nu P^n = \nu$ for all $n \ge 0$. Consider $\sum_i \nu(i)\,\mathbb{E}_i[V_j(n)]/n$ — since $\mathbb{E}_i[V_j(n)] = \sum_{k=0}^{n-1}p_{ij}^{(k)}$ and $\nu$ is stationary, $\sum_i \nu(i) p_{ij}^{(k)} = \nu(j)$ for every $k$, so

But $V_j(n)/n$ is a bounded ($\le 1$) sequence converging a.s. (by Step 4, valid started from any state, hence from $\nu$ by conditioning) to the constant $\pi(j)$; by the Bounded Convergence Theorem, $\mathbb{E}_\nu[V_j(n)/n] \to \pi(j)$. Comparing the two, $\nu(j) = \pi(j)$ for every $j$. Hence the stationary distribution is unique and equals the $\pi$ constructed above. This proves part (1) and finishes the almost-sure convergence claim of part (2), where "regardless of the initial distribution" follows because Step 4's argument only used that the chain a.s. reaches $i$ eventually (guaranteed by irreducibility from any start) and is thereafter a copy of the chain started at $i$.

Step 7: Extend to bounded functions $f$ (part 3). Let $f: S \to \mathbb{R}$ be bounded, $|f| \le M < \infty$. For finite $S$, or more generally when $\sum_j |f(j)|\pi(j) < \infty$ (automatic if $f$ is bounded, since $\sum_j \pi(j) = 1$),

If $S$ is finite this is a finite sum of terms each converging a.s. by part (2), so the whole sum converges a.s. to $\sum_j f(j)\pi(j)$. If $S$ is countably infinite, fix $\varepsilon>0$ and choose a finite set $F \subset S$ with $\sum_{j \notin F}\pi(j) < \varepsilon$ (possible since $\pi$ is a probability measure); one shows, using $(\ast\ast)$-type renewal bounds uniformly summable over $j \notin F$ (justified because $\sum_{j\notin F}\gamma_i(j) = m_i - \sum_{j \in F}\gamma_i(j) \to 0$ as $F \uparrow S$, an immediate consequence of $\sum_j \gamma_i(j)=m_i<\infty$ and dominated convergence for the series), that the tail contribution $\sum_{j\notin F} f(j) V_j(n)/n$ is a.s. eventually bounded by $2M\varepsilon$, while the finite part converges exactly as in the finite case; letting $\varepsilon \to 0$ gives the general result. $\blacksquare$