Stationary Ergodic Sources and Universal Coding — Examples

Partition the coordinates into consecutive blocks of lengths $L_j=2^{2^j}$ for $j\ge 1$. In odd-numbered blocks set $X_i=0$ deterministically; in even-numbered blocks let the $X_i$ be fair independent bits. Independence gives the block law $p_{0:N-1}(x_0^{N-1})={\prod }_{i=0}^{N-1}{p}_i(x_i)$. Expanding its finite entropy sum over positive-probability words and using ${\log }_2{\prod }_i{p}_i(x_i)={\sum }_i{\log }_2{p}_i(x_i)$ yields $H(X_0^{N-1})={\sum }_{i=0}^{N-1}H(X_i),$ since each other coordinate probability sums to one. Thus the entropy contribution is zero on odd blocks and one bit per coordinate on even blocks.

Let $N_j={\sum }_{r=1}^j{L}_r$ be the endpoint of block $j$. For $j\ge 2$, ${\sum }_{r<j}{L}_r\le (j-1)2^{2^{j-1}}$, so $\frac{L_j}{{\sum }_{r<j}{L}_r}\ge \frac{2^{2^{j-1}}}{j-1}⟶\mathrm{\infty }\mathrm{.}$ Thus the previous blocks contribute a vanishing fraction of $N_j$. Therefore $H(X_0^{N_j-1})\mathrm{/}{N}_j\to 0$ along odd $j$ and tends to $1$ along even $j$. The block entropy per symbol has no limit, so the process has no entropy rate in the sense of [F2].

Applying the longest-dictionary-prefix rule successively gives phrases $0,1,00,10,100,1\mathrm{\#}$. The records are respectively $(0,0),(0,1),(1,0),(2,0),(4,0),(2,\mathrm{\#})$; after the first five records the dictionary indices $1$ through $5$ name $0,1,00,10,100$. The sixth record terminates without insertion.

The dictionary trie has root index $0$, edges $0$ and $1$ to nodes $1$ and $2$, then edge $0$ from node $1$ to node $3$, edge $0$ from node $2$ to node $4$, and edge $0$ from node $4$ to node $5$. The dashed edge marked $\mathrm{\#}$ from node $2$ is the final output phrase only; it is not a dictionary node. Each node label gives its dictionary index and phrase; each edge label is the symbol appended to the parent's phrase, and the root phrase is empty. The diagram's ordinary nodes are exactly the phrases inserted after the first five records; the terminal edge is drawn dashed because [F1] does not insert it.

Starting with the root, the decoder expands the listed records to the same six phrases; concatenating them yields $0100101001\mathrm{\#}$. It stops at $\mathrm{\#}$, so deleting the marker recovers the input exactly, as guaranteed by [F2].

For fair IID bits, every length-$n$ word has probability $2^{-n}$; hence $H_n=n$ and $h=1$ bit per symbol. The shift is stationary by product-law invariance, and [F4] gives expected LZ78 rate tending to one.

For the Markov source, take stationary law $\pi =(1\mathrm{/}2,1\mathrm{/}2)$ and transition matrix $K$ with diagonal entries $3\mathrm{/}4$ and off-diagonal entries $1\mathrm{/}4$; direct multiplication gives $\pi K=\pi$. Its length-$n$ block probabilities are $P(X_0^{n-1}=x_0^{n-1})=\frac{1}{2}{\prod }_{i=1}^{n-1}{K}_{x_{i-1},x_i}\mathrm{.}$ Expanding the finite entropy sum with this factorization gives $H_n=H(X_0)+{\sum }_{i=1}^{n-1}H(X_i\mid X_{i-1})=1+(n-1)H_2(1\mathrm{/}4),$ where $H_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. Thus $h=H_2(1\mathrm{/}4)\approx 0.811278$. The stationary LZ78 expected-rate theorem [F4] gives the same limiting rate without an ergodicity assumption.

The distinct rates arise because IID entropy counts each bit without context, while the Markov transition entropy conditions on the previous state. Both examples have positive entropy, and the computed limits are consistent with $0\le h\le 1$.