Stationary Ergodic Sources and Universal Coding

A basic product cylinder restricts only finitely many coordinates. Its inverse image under $T$ imposes the same restrictions on the coordinates shifted by one, so is again a product cylinder and is measurable. Since product cylinders generate the product sigma-algebra and inverse image preserves complements and countable unions, $T$ is measurable on that sigma-algebra. Call $P$ stationary when it is measure preserving under this measurable shift, precisely the condition in [F1].

For a stationary $P$, call the source ergodic when each event $E$ satisfying $T^{-1}E=E$ has $P(E)\in \{0,1\}$; by [F2] this is exactly ergodicity of the probability system.

Define ${\log }_{2}t:=\ln t\mathrm{/}\ln 2$ for $t>0$. The denominator is positive because $2>1$, $\ln$ is strictly increasing, and $\ln 1=0$ by [F2]. For every positive-probability block $x$, define its information in bits by $I_n^{(2)}(x)=-{\log }_2{p}_n(x)$; values on zero-probability blocks may be set to $+\mathrm{\infty }$ because they are never sampled.

Define block entropy in bits by $H_n^{(2)}:=\mathbb{E}{I}_n^{(2)}(X_0^{n-1})=H_{\mathrm{n}\mathrm{a}\mathrm{t}}(p_n)\mathrm{/}\ln 2.$ Finite summation and [F1] show this equals $-{\sum }_{x:p_n(x)>0}{p}_n(x){\log }_2{p}_n(x)$. Thus the library's entropy interface stays in nats while this page's information and coding rates use bits. For any probability law $p$ on a finite set, put $H_2(p):=H_{\mathrm{n}\mathrm{a}\mathrm{t}}(p)\mathrm{/}\ln 2=-{\sum }_{x:p(x)>0}p(x){\log }_{2}p(x)$, and write $H_2(U):=H_2(P_U)$ for a finite-valued random variable $U$. For finite-valued $U,V$, also define conditional entropy by $H_2(U\mid V)={\sum }_{v:P(V=v)>0}P(V=v)H_2(P_{U\mid V=v})$; zero-probability conditioning values are omitted.

One codeword determines its message by injectivity. In the singleton empty-word case, a known count determines the unique message list, whereas distinct unknown counts all give the same empty string. In particular, the empty string describes one known block with length zero.

If all codewords are nonempty, at most one codeword can prefix an unread concatenation, because any two such prefixes would be comparable by the prefix relation and injectivity excludes equal codewords for different messages. Remove that nonempty codeword and repeat; the finite unread length decreases, so this recovers the complete message list without a supplied count.

For each $K$, put $U_K={\sup }_{j\ge K}\mathrm{\mid }{g}_j-g\mathrm{\mid }$. Then $U_K\downarrow 0$ $\mu$-almost everywhere and $0\le U_K\le 2G$ almost everywhere, since $g\le G$ as a pointwise limit. Dominated convergence [F4] gives $\int U_{K}d\mu \to 0$.

Since $g_i\to g$ almost everywhere and $\mathrm{\mid }{g}_i-g\mathrm{\mid }\le 2G$, [F4] gives $\int \mathrm{\mid }{g}_i-g\mathrm{\mid }d\mu \to 0$. By [F3, F5], $\int \mathrm{\mid }{g}_i-g\mathrm{\mid }\circ T^{i}d\mu =\int \mathrm{\mid }{g}_i-g\mathrm{\mid }d\mu$, so linearity [F7] makes the integral of the absolute triangular error $n^{-1}{\sum }_{i<n}\int \mathrm{\mid }{g}_i-g\mathrm{\mid }d\mu \to 0$ by Cesaro averaging. Thus the error tends to zero in $L^1(\mu )$.

Fix $K$. For $i\ge K$, $\mathrm{\mid }{g}_i-g\mathrm{\mid }\le U_K$. Hence for $n>K$, the average of $\mathrm{\mid }{g}_i-g\mathrm{\mid }\circ T^i$ is bounded by the first $K$ terms divided by $n$, plus $n^{-1}{\sum }_{i=K}^{n-1}{U}_K\circ T^i$. The first part tends to zero almost everywhere. By [F1], the second part converges almost everywhere to the Birkhoff limit $U_K^{\ast }$; by [F2], the averages converge to $U_K^{\ast }$ in $L^1(\mu )$. By [F3, F5, F7], every average has integral $\int U_{K}d\mu$. Thus [F6] and the $L^1$ convergence give $\mid \int U_{K}d\mu -\int U_K^{\ast }d\mu \mid \le \mathrm{\parallel }{A}_n{U}_K-U_K^{\ast }{\mathrm{\parallel }}_1\to 0$. Therefore $U_K^{\ast }\in L^1(\mu )$ and $\int U_K^{\ast }d\mu =\int U_{K}d\mu$.

Apply step 2.1 to every integer $K$ on the intersection of the resulting countably many full-measure sets. The limsup of the left side is at most $U_K^{\ast }$ for each $K$. Since $U_K$ decreases pointwise, the averages and their limits $U_K^{\ast }$ decrease almost everywhere. They are nonnegative and bounded by the integrable $U_1^{\ast }$; dominated convergence [F4] gives $\int {\inf }_K{U}_K^{\ast }d\mu ={\lim }_K\int U_K^{\ast }d\mu ={\lim }_K\int U_{K}d\mu =0$. Thus ${\inf }_K{U}_K^{\ast }=0$ almost everywhere, and the limsup is zero. Therefore $n^{-1}{\sum }_{i<n}\mathrm{\mid }{g}_i-g\mathrm{\mid }(T^i\omega )\to 0$ almost everywhere.

By [F1]–[F2], the Birkhoff averages of $g$ converge almost everywhere and in $L^1(\mu )$ to their Birkhoff limit. Steps 3.1 and 1.2 show the triangular averages differ from these averages by quantities tending to zero almost everywhere and in $L^1(\mu )$, respectively. Hence both modes of convergence hold with the same limit.

The integral logarithm is the natural logarithm by [F3] and [F5]. If $t>1$, then $1\mathrm{/}u\le 1$ on $[1,t]$, so [F2]–[F4] give $\ln t={\int }_1^{t}du\mathrm{/}u\le t-1$. If $0<t<1$, then $1\mathrm{/}u\ge 1$ on $[t,1]$, so ${\int }_t^{1}du\mathrm{/}u\ge 1-t$; [F3] and [F7] give $\ln t=-{\int }_t^{1}du\mathrm{/}u\le t-1$. At $t=1$, [F6] gives equality. Therefore $\ln t\le t-1$ for all $t>0$.

Apply step 1.1 to $t=q_i\mathrm{/}{p}_i$ for every $i$ with $p_i>0$. Then ${\sum }_{i:p_i>0}{p}_i\ln (p_i\mathrm{/}{q}_i)=-{\sum }_{i:p_i>0}{p}_i\ln (q_i\mathrm{/}{p}_i)\ge {\sum }_{i:p_i>0}(p_i-q_i)=1-{\sum }_{i:p_i>0}{q}_i\ge 0.$ Dividing by $\ln 2>0$ gives the same nonnegativity for the bit-log sum. Thus finite KL nonnegativity against a subprobability reference, as well as the logarithm inequality used to prove it, follows from finite sums and elementary integral bounds; no choice axiom enters.

Inverse images of product cylinders under $T$ are product cylinders; since these generate the product sigma-algebra, $T$ is measurable. The law $P$ is asymptotically mean stationary (AMS) when for every measurable event $E$ the limit $\bar{P}(E)={\lim }_{N\to \mathrm{\infty }}\frac{1}{N}{\sum }_{j=0}^{N-1}P(T^{-j}E)$ exists and the resulting set function is a probability measure.

For each measurable $E$, the Ces`aro averages for $T^{-1}E$ and $E$ differ by $\frac{1}{N}{\sum }_{j=0}^{N-1}P(T^{-(j+1)}E)-\frac{1}{N}{\sum }_{j=0}^{N-1}P(T^{-j}E)=\frac{P(T^{-N}E)-P(E)}{N}\mathrm{.}$ The numerator has absolute value at most $1$, so its quotient tends to zero. Taking limits, which exist by step 1.1 for both events, gives $\bar{P}(T^{-1}E)=\bar{P}(E)$. Thus the Ces`aro limit is stationary in the sense of [F1].

The resulting law $\bar{P}$ is called the stationary mean when it is stationary in the sense of [F1]. If $E$ is strictly shift invariant, then each summand $P(T^{-j}E)=P(E)$; hence $P(E)=\bar{P}(E)$. Tail events are handled by the separate domination lemma, not by this invariant-event identity.

Call the AMS source ergodic when its stationary mean $\bar{P}$ is ergodic as a measure-preserving system under the same shift. This is a property of the mean, not a claim that $P$ itself is stationary.

If $d(e(x))=x$ for every $x\in {\mathcal{A}}^n$, then $e$ is injective: $e(x)=e(y)$ implies $x=d(e(x))=d(e(y))=y$. Conversely, if $e$ is injective, its inverse on the image is well-defined; a decoder is lossless exactly when it agrees with that inverse there, and its values off the image are irrelevant.

If $x,y\in S$ and $e(x)=e(y)$, then $x=d(e(x))=d(e(y))=y$. Thus $e$ restricted to $S$ is injective, and the finite set $S$ has cardinality at most $\mathrm{\mid }M\mathrm{\mid }\le 2^{\lfloor nR\rfloor }$. Its error probability is $P_n(S^c)$ by definition.

An information-lossless $s$-state encoder consists of a finite state set $S$, an initial state, an update map $g:S\times \mathcal{A}\to S$, and an output map $f:S\times \mathcal{A}\to \{0,1{\}}^{\ast }$. It is information-lossless when for each initial state the map from finite input words to (concatenated output, final state) is injective.

The encoder class is nonempty: let $t=\max (1,\lceil {\log }_2\mathrm{\mid }\mathcal{A}\mathrm{\mid }\rceil )$ and choose distinct $t$-bit labels for the finitely many source symbols. Use one state with the identity update and emit each symbol's label. The output splits into fixed-width labels and therefore uniquely determines every finite input word. Let $L_E(x_0^{n-1})$ be an encoder's concatenated output length and set ${\rho }_s(x)={\inf }_E{\mathrm{lim\hspace{0.17em}sup}}_n{L}_E(x_0^{n-1})\mathrm{/}n$, over information-lossless encoders with at most $s$ states. Define finite-state compressibility ${\rho }_{\mathrm{F}\mathrm{S}}(x)={\inf }_{s\ge 1}{\rho }_s(x)$. The infima are nonincreasing in $s$ and bounded below by zero, so the limit in the equivalent notation ${\lim }_{s\to \mathrm{\infty }}{\rho }_s(x)$ exists.

Define the upper information rate $\bar{h}(P):={\mathrm{lim\hspace{0.17em}sup}}_{n\to \mathrm{\infty }}{H}_n\mathrm{/}n$ and, when the limsup and liminf agree, the information rate $h(P):={\lim }_{n\to \mathrm{\infty }}{H}_n\mathrm{/}n$. This definition does not assume stationarity.

Every positive block probability is at most one, so the finite-sum formula in [F1] gives $H_n\ge 0$. Let $N=\mathrm{\mid }\mathcal{A}{\mathrm{\mid }}^n$ and compare the block law $p_n$ with the uniform law $q(x)=1\mathrm{/}N$ on the nonempty finite set ${\mathcal{A}}^n$. By [F2], $0\le {\sum }_{x:p_n(x)>0}{p}_n(x){\log }_2\frac{p_n(x)}{q(x)}=-H_n+{\log }_{2}N\mathrm{.}$ Hence $H_n\le {\log }_{2}N=n{\log }_2\mathrm{\mid }\mathcal{A}\mathrm{\mid }$. Consequently the upper information rate is defined and lies in $[0,{\log }_2\mathrm{\mid }\mathcal{A}\mathrm{\mid }]$, and whenever the information-rate limit exists it lies in the same interval.

Define the backward recurrence time of the current length-$n$ block by $R_n(x)=\inf \{j\ge 1:(x_{-j},\dots ,x_{-j+n-1})=(x_0,\dots ,x_{n-1})\},$ with $R_n=+\mathrm{\infty }$ if the set is empty. The start offset is positive, so the current block is not counted as its own match.

Define its previous-match phrase length in a window of width $W$ by $L_W(x)=\max (\{0\}\cup \{n\ge 1:R_n(x)\le W\}),$ with maximum $+\mathrm{\infty }$ when the set is unbounded. The set is nonempty because it contains $0$; if a length-$m$ block matches at offset $j$, every shorter positive prefix also matches at the same offset, so the matched lengths form an initial segment. The empty match of length zero is always allowed.

For a periodic sequence, $L_W$ can be infinite; the recurrence-time theorem will only be used to infer the logarithmic inverse relation in probability when $h>0$.

For $k\ge 0$, let ${\mathcal{F}}_k=\sigma (X_{-k},\dots ,X_{-1})$, with ${\mathcal{F}}_0$ trivial. For each $a\in \mathcal{A}$, define $p_k(a)=P(X_0=a\mid {\mathcal{F}}_k)$ by averaging over the finite atoms of ${\mathcal{F}}_k$, and put $g_k=-{\log }_2{p}_k(X_0)$ on the event $p_k(X_0)>0$, with arbitrary value on its null complement.

The selected probability is positive almost surely: on each atom $B\in {\mathcal{F}}_k$ with $P(B)>0$, $P(X_0=a\mid B)=0$ implies $P(B\cap \{X_0=a\})=0$. Thus $g_k$ is finite almost surely; [F1] identifies the same distributions after shifting any finite window.

Put $r(x)=2^{-\mathrm{\ell }(x)}>0$ on the positive support. By [F3], ${\sum }_{x}r(x)\le 1$, so [F4] gives $0\le {\sum }_{x}p(x){\log }_2(p(x)\mathrm{/}r(x))=-H(p)+{\sum }_{x}p(x)\mathrm{\ell }(x)$. Thus every such code has expected length at least $H(p)$. If the support has one point, one known block can be described by length zero and both entropy and optimal expected length are zero; no unknown message-count decoding is claimed.

Assume now that the support has at least two points. Then every positive $p(x)<1$, so $\mathrm{\ell }(x)=\lceil -{\log }_{2}p(x)\rceil$ is a positive integer. It satisfies ${\sum }_x{2}^{-\mathrm{\ell }(x)}\le {\sum }_{x}p(x)=1$, so the finite binary Kraft criterion gives a prefix code. Also $\mathrm{\ell }(x)<-{\log }_{2}p(x)+1$, hence its expected length is less than $H(p)+1$.

For singleton support step 1.1 gives $L^{\ast }(p)=H(p)=0<H(p)+1$. For support of size at least two, taking the infimum over all prefix codes in step 1.1 and using the code constructed in step 2.1 proves $H(p)\le L^{\ast }(p)<H(p)+1$. Empty support cannot occur for a probability vector.

On every positive-probability block, factor its probability into successive conditional probabilities by repeated use of $P(A\cap B)=P(A)P(B\mid A)$. Taking $-{\log }_2$ and averaging over the finite support yields $H(X_0^{n-1})={\sum }_{i=0}^{n-1}H(X_i\mid X_0^{i-1})\mathrm{.}$ The $i=0$ term is $H(X_0)$.

For finite random variables $U,V$, the same factorization gives $H_2(U,V)=H_2(U)+H_2(V\mid U)$. Terms with $P(U=u)=0$ contribute zero, so no conditional law on a null event affects the identity.

For finite $U,V,W$, fix any $v$ with $P(V=v)>0$. The conditional mutual information at that value is ${\sum }_{w}P(w\mid v)D_2(P_{U\mid v,w}\mathrm{\parallel }{P}_{U\mid v})\ge 0$ by [F2]; if a conditional reference probability is zero, every positive-weight conditional law also assigns that outcome zero, so all displayed divergences are defined on their supports. Averaging over $v$ gives $H_2(U\mid V)-H_2(U\mid V,W)\ge 0$.

If $h<0$, then the nonnegative variable $I_n(X^n)\mathrm{/}n$ stays at distance at least $-h$ from $h$, contradicting convergence in probability; hence $h\ge 0$. Let $R>h$ and choose $ϵ>0$ with $h+ϵ<R$. Define $T_n=\{x:p_n(x)>0,I_n(x)\le n(h+ϵ)\}$. On $T_n$, each word has probability at least $2^{-n(h+ϵ)}$, so $\mathrm{\mid }{T}_n\mathrm{\mid }\le 2^{n(h+ϵ)}$. The AEP gives $P(X^n\in T_n)\to 1$.

For all sufficiently large $n$, $\mathrm{\mid }{T}_n\mathrm{\mid }\le 2^{\lfloor nR\rfloor }$, since $R-h-ϵ>0$. Fix an enumeration of the finite alphabet $\mathcal{A}$ once, and let $a_0$ be its first symbol. For each such $n$, order $T_n$ lexicographically, take $M_n=\{0,1{\}}^{\lfloor nR\rfloor }$ in lexicographic order, and map the $j$th typical block to the $j$th binary word. Define $e_n$ by this assignment on $T_n$ and by $e_n(x)=0^{\lfloor nR\rfloor }$ otherwise. Define $d_n$ to return each typical block on its assigned message and $a_0^n$ on all remaining messages. This is a rate-$R$ code in the sense of [F2], and every block in $T_n$ is decoded correctly. Its error is at most $P(X^n\mathrm{\notin }{T}_n)\to 0$. For the finitely many earlier $n$, take $e_n$ constant at the all-zero message and $d_n$ constant at $a_0^n$.

Let $0\le R<h$ and choose $ϵ>0$ with $R+ϵ<h$. For any rate-$R$ code, its success set $S_n$ has at most $2^{\lfloor nR\rfloor }$ words by [F2]. Split it according to whether $I_n(x)>n(R+ϵ)$. The probability of successful words in that part is at most $2^{nR}{2}^{-n(R+ϵ)}=2^{-nϵ}$, while the other part has total probability tending to zero by the AEP. Thus success probability tends to zero. At $R=h$ neither conclusion is asserted.