Shannon–McMillan limit for finite-alphabet AMS ergodic sources

If $q=1$, the source path is deterministic, every block has probability one, and $h=0$, so the claim holds. Assume henceforth $q\ge 2$. Fix $k\ge 1$. For each prefix $u\in {\mathcal{A}}^k$, the finite conditional probabilities $r_{n,k}(u)=P(X_0^{k-1}=u\mid X_k^{n-1}),n>k,$ form a bounded martingale as the conditioning sigma-algebras increase. For each rational $a<b$ in $[0,1]$, the buy-at-$a$, sell-at-$b$ strategy has expected gain zero; every completed upcrossing earns at least $b-a$ and the final unsold position loses at most one. Thus the expected upcrossing count through any horizon is at most $(b-a{)}^{-1}$. The counts increase with the horizon, so [F8] gives finite expected total count and hence finitely many upcrossings almost surely. Since a bounded real sequence that fails to converge has infinitely many upcrossings of some rational interval, countability of the rational pairs, prefixes and fixed $k$ implies $r_{n,k}(u)$ converges almost surely.

For each finite future cylinder $B\in \sigma (X_k,\dots ,X_{n-1})$, the conditional-probability identity gives ${\int }_B{r}_{n,k}(u)dP=P(B\cap \{X_0^{k-1}=u\})$. As $n$ increases these conditional probabilities converge almost surely and lie in $[0,1]$, so [F7] gives the same identity with $r_{\mathrm{\infty },k}(u)$. The finite future cylinders form an algebra generating $\sigma (X_k,X_{k+1},\dots )$. The finite measures $B\mapsto {\int }_B{r}_{\mathrm{\infty },k}(u)dP$ and $B\mapsto P(B\cap \{X_0^{k-1}=u\})$ agree on that algebra; their agreement class is a monotone class by continuity of finite measures, so [F6] extends the identity to the full future sigma-algebra. Thus $r_{\mathrm{\infty },k}(u)$ is a version of the conditional probability of the prefix event given the full future. Therefore $P(X_0^{k-1}=u,r_{\mathrm{\infty },k}(u)=0)=\int 1_{\{r_{\mathrm{\infty },k}(u)=0\}}{r}_{\mathrm{\infty },k}(u)dP=0.$ Since there are finitely many prefixes, the realized-prefix conditional probability converges to a positive value almost surely. Consequently, for fixed $k$, $b_{n,k}^P:=n^{-1}\mid {\log }_{2}P(X_0^{k-1}\mid X_k^{n-1})\mid \to 0P\text{-a.s.},$ and the same holds for $b_{n,k}^{\bar{P}}$ under $\bar{P}$.

For each integer $m$, use the fixed-$k$ limits for $k\le m$ and both measures to choose a deterministic $N(m)$, increasing with $m$, such that $P({\sup }_{n\ge N(m),k\le m}{b}_{n,k}^P>1\mathrm{/}m)+\bar{P}({\sup }_{n\ge N(m),k\le m}{b}_{n,k}^{\bar{P}}>1\mathrm{/}m)<2^{-m}\mathrm{.}$ Let $k(n)=\max \{m:N(m)\le n,m\le \sqrt{n}\}$, taking $k(n)=1$ for the finitely many initial $n$ where the set is empty. Then $k(n)\to \mathrm{\infty }$, $k(n)\mathrm{/}n\to 0$, and [F5] implies that the prefix-to-suffix log-probability boundary divided by $n$ tends to zero almost surely under both $P$ and $\bar{P}$. Under $\bar{P}$, the finite conditional-probability identity gives $-\frac{1}{n}{\log }_2\bar{P}(X_{k(n)}^{n-1})=-\frac{1}{n}{\log }_2\bar{P}(X_0^{n-1})-b_{n,k(n)}^{\bar{P}}$ almost surely for all sufficiently large $n$. By [F4] and the boundary convergence just proved, the right side tends to $h$. Its failure event is in the future-tail sigma-algebra: for every fixed $j$, all sufficiently large $n$ have $k(n)\ge j$, so the suffix terms depend only on coordinates from $j$ onward. Thus [F3] gives $-n^{-1}{\log }_2\bar{P}(X_{k(n)}^{n-1})\to hP\text{-a.s.}$

For each $n$ and $ϵ>0$, summing over suffix words $w$ gives $\bar{P}\text{\hspace{0.17em}⁣}(\frac{P(w)}{\bar{P}(w)}\ge 2^{nϵ})\le 2^{-nϵ},P\text{\hspace{0.17em}⁣}(\frac{\bar{P}(w)}{P(w)}\ge 2^{nϵ})\le 2^{-nϵ},$ where the event is evaluated at the observed suffix $w=X_{k(n)}^{n-1}$. For example, on the first event $\bar{P}(w)\le 2^{-nϵ}P(w)$, and summing over its words proves the first inequality; the second is symmetric. For any fixed $j$, all sufficiently large $n$ have $k(n)\ge j$, so the forward-ratio limsup event is measurable with respect to coordinates from $j$ onward. By [F5], the reverse-ratio violations occur only finitely often $P$-almost surely, while the forward-ratio violation limsup is a $\bar{P}$-null tail event and hence is $P$-null by [F3]. Applying this for every positive rational $ϵ$ yields $n^{-1}{\log }_2\frac{P(X_{k(n)}^{n-1})}{\bar{P}(X_{k(n)}^{n-1})}\to 0P\text{-a.s.}$ Interpret a ratio with positive numerator and zero denominator as $+\mathrm{\infty }$. The observed $P$-suffix has positive $P$-probability almost surely for every $n$; the forward-ratio limsup argument also excludes zero $\bar{P}$-suffix probabilities for all sufficiently large $n$, $P$-almost surely.

Step 3.1 makes the normalized log probability of the P-prefix differ from that of its suffix by a quantity tending to zero; step 4.1 makes the P- and $\bar{P}$-suffix log probabilities have the same normalized limit; and step 3.1 identifies the latter as $-h$. Therefore $-\frac{1}{n}{\log }_{2}P(X_0^{n-1})⟶hP\text{-almost surely}\mathrm{.}$ The argument includes $h=0$ and makes no claim of an exponential convergence rate. AC is used only through [A1], [F3].