Ergodic theorem for an irreducible positive-recurrent Markov chain

By [F2], ${\mathbb{E}}_x{T}_x^{+}=1\mathrm{/}\pi (x)\in (0,\mathrm{\infty })$ and $\pi (x)>0$; by [F1], the finite return mean makes $x$ positive recurrent and therefore recurrent.

By the class property [F4], every state of the irreducible chain is recurrent, although only the recurrence of $x$ is needed below.

Let $R_0=0<R_1<R_2<\cdots$ be the successive return times of the chain to $x$ and define the cycle lengths and cycle rewards $L_k:=R_k-R_{k-1}$, $W_k:={\sum }_{j=R_{k-1}}^{R_k-1}f(X_j)$ for $k\ge 1$. By [F3] all $R_k$ are finite almost surely and the excursions are iid; hence $(L_k,W_k{)}_{k\ge 1}$ is an iid sequence of pairs, with $(L_1,W_1)$ distributed as $(T_x^{+},{\sum }_{n<T_x^{+}}f(X_n))$ under ${\mathbb{P}}_x$, and $L_k\ge 1$.

The reward is integrable. Put $N_y:={\sum }_{n<T_x^{+}}{\mathbf{1}}_{\{X_n=y\}}$, so ${\mathbb{E}}_x{N}_y={\mu }_x(y)=\pi (y)\mathrm{/}\pi (x)$ and ${\mathbb{E}}_x{T}_x^{+}=1\mathrm{/}\pi (x)$ by [F2]. Enumerate the countable set $E$ and apply monotone convergence [F6] to increasing finite sums of $\mathrm{\mid }f(y)\mathrm{\mid }{N}_y$; their pointwise limit equals ${\sum }_{n<T_x^{+}}\mathrm{\mid }f(X_n)\mathrm{\mid }$, since each time $n<T_x^{+}$ contributes to exactly one state. Thus ${\mathbb{E}}_x{\sum }_{n<T_x^{+}}\mathrm{\mid }f(X_n)\mathrm{\mid }={\sum }_y\mathrm{\mid }f(y)\mathrm{\mid }{\mu }_x(y)={\sum }_y\pi (y)\mathrm{\mid }f(y)\mathrm{\mid }\mathrm{/}\pi (x)<+\mathrm{\infty }$. Define $U_1^{\pm }:={\sum }_{n<T_x^{+}}{f}^{\pm }(X_n)$, the cycle rewards of the positive and negative parts of $f$. The same nonnegative calculation gives ${\mathbb{E}}_x{U}_1^{\pm }={\sum }_y\pi (y)f^{\pm }(y)\mathrm{/}\pi (x)<\mathrm{\infty }$. Since $W_1=U_1^{+}-U_1^{-}$ and $\mathrm{\mid }{W}_1\mathrm{\mid }\le U_1^{+}+U_1^{-}={\sum }_{n<T_x^{+}}\mathrm{\mid }f(X_n)\mathrm{\mid }$ almost surely, $W_1$ is integrable; linearity [F7] yields ${\mathbb{E}}_x{W}_1={\sum }_y\pi (y)f(y)\mathrm{/}\pi (x)$. In general $U_1^{\pm }$ are not the positive and negative parts of $W_1$. Also ${\mathbb{E}}_x{L}_1=1\mathrm{/}\pi (x)$.

By the strong law [F5] applied to the iid sequences $(L_k)$ and $(W_k)$: $\frac{1}{m}{\sum }_{k=1}^m{L}_k\to \frac{1}{\pi (x)}$ and $\frac{1}{m}{\sum }_{k=1}^m{W}_k\to \frac{{\sum }_y\pi (y)f(y)}{\pi (x)}$ almost surely; consequently $R_m\mathrm{/}m\to 1\mathrm{/}\pi (x)>0$, so $R_m\to \mathrm{\infty }$ and $R_{m+1}\mathrm{/}{R}_m\to 1$ almost surely.

If $f\equiv 0$ both sides vanish; if $f$ is unbounded but $\pi$-integrable its excursion rewards are still integrable by step 3.1, and no boundedness is used.

First suppose $f\ge 0$, so each $W_k\ge 0$ and the partial sums $S_m:={\sum }_{k=1}^m{W}_k$ are nondecreasing. Let $R_m\le n<R_{m+1}$; then $S_m\le {\sum }_{j=0}^{n-1}f(X_j)\le S_{m+1}$, while $R_m\le n<R_{m+1}$, so, for $m\ge 1$, $\frac{S_m}{R_{m+1}}\le \frac{1}{n}{\sum }_{j<n}f(X_j)\le \frac{S_{m+1}}{R_m}$. Since $m=m(n)\to \mathrm{\infty }$ almost surely by step 4.1, $\frac{S_m}{R_m}=\frac{S_m\mathrm{/}m}{R_m\mathrm{/}m}\to {\sum }_y\pi (y)f(y)$ and $\frac{R_{m+1}}{R_m}\to 1$, so both bounding sequences converge to ${\sum }_y\pi (y)f(y)$, and the sandwiched average does too.

For general real-sign $f$, write $f=f^{+}-f^{-}$ with $f^{\pm }\ge 0$; by step 3.1 both functions satisfy ${\sum }_y\pi (y)f^{\pm }(y)\le {\sum }_y\pi (y)\mathrm{\mid }f(y)\mathrm{\mid }<\mathrm{\infty }$, so step 5.1 applies to each, and subtracting the two almost-sure limits gives $\frac{1}{n}{\sum }_{j<n}f(X_j)\to {\sum }_y\pi (y)f^{+}(y)-{\sum }_y\pi (y)f^{-}(y)={\sum }_y\pi (y)f(y)$ almost surely.

The argument does not assume aperiodicity, since it uses return epochs and cycle laws; if $E$ is a singleton the conclusion is the constant identity; and $S_m\mathrm{/}{R}_m$ is formed only for $m\ge 1$, where $R_m\ge m\ge 1$, so there is no division by zero.

For complex $f$ apply step 6.1 to $\mathrm{Re}f$ and $\mathrm{Im}f$, which satisfy the same absolute-integrability hypothesis, and recombine. The arbitrary starting state $x$ was fixed once and for all at the beginning; the argument is uniform in $x$ because $x$ enters only through the bounds ${\mathbb{E}}_x{T}_x^{+}=1\mathrm{/}\pi (x)$ and ${\mu }_x=\pi \mathrm{/}\pi (x)$.

If $f\ge 0$, step 5.1 suffices; step 6.1 records the signed reduction.

AC [A1] is used exactly at the AC-qualified supplier applications in steps 1.1, 2.2, and 3.1; the strong law and the sandwich/reduction arguments use no further choice.