Entropy-rate limit for a stationary finite-alphabet source

By the chain rule, $H(X_0^{n+m-1})=H(X_0^{n-1})+H(X_n^{n+m-1}\mid X_0^{n-1})\le H_n+H_m$. The inequality follows because conditioning cannot increase entropy, and stationarity makes $H(X_n^{n+m-1})=H_m$. Thus $(H_n)$ is subadditive.

Fix $k\ge 1$ and write $n=ak+r$ with $0\le r<k$. Repeated subadditivity gives $H_n\le a{H}_k+H_r$, where $H_0=0$ and the finitely many $H_r$ are bounded by $k{\log }_2\mathrm{\mid }\mathcal{A}\mathrm{\mid }$. Hence ${\mathrm{lim\hspace{0.17em}sup}}_n{H}_n\mathrm{/}n\le H_k\mathrm{/}k$. Since $H_n\mathrm{/}n\ge {\inf }_{j\ge 1}{H}_j\mathrm{/}j$, taking the infimum over $k$ proves the limit exists and equals $h={\inf }_{k\ge 1}{H}_k\mathrm{/}k$.

For each $k\ge 0$, put $a_k=H(X_0\mid X_{-k}^{-1})$, with $a_0=H(X_0)$ for the empty past. By the conditioning monotonicity in [F3], $(a_k)$ is nonincreasing; it is bounded below by zero, so it has a limit $a_{\mathrm{\infty }}$. The chain rule gives $H_n={\sum }_{i=0}^{n-1}H(X_i\mid X_0^{i-1})\mathrm{.}$ By stationarity [F1], $H(X_i\mid X_0^{i-1})=H(X_0\mid X_{-i}^{-1})=a_i$. Therefore $H_n\mathrm{/}n=n^{-1}{\sum }_{i=0}^{n-1}{a}_i\to a_{\mathrm{\infty }}$ by Ces`aro convergence. Comparing with the limit $h$ from step 2.1 yields $h=a_{\mathrm{\infty }}$, the limit of finite-past conditional entropies. By [F4], $h$ is finite and lies in $[0,{\log }_2\mathrm{\mid }\mathcal{A}\mathrm{\mid }]$, including deterministic sources with $h=0$.