LZ78 expected-rate universality for stationary sources

Adjoining an unused symbol, if necessary, does not change any block probability, block entropy or entropy rate: every word containing the extra symbol has probability zero. Stationarity is retained under the coordinatewise inclusion. The resulting coding alphabet has $q\ge 2$, so the stated terminated algorithm is defined, including for an originally singleton source with $h=0$. Let $N$ be the number of phrases in parsing $X_0^{n-1}\mathrm{\#}$ over the augmented alphabet $\mathcal{A}\cup \{\mathrm{\#}\}$, and let $c_{\mathrm{\ell },u}$ count phrases of length $\mathrm{\ell }$ and preceding $k$-symbol context $u$. The phrases are distinct. For $r=\lfloor \frac{1}{2}{\log }_{q+1}(n+1)\rfloor$, at most ${\sum }_{j=1}^r(q+1{)}^j=O(\sqrt{n})$ phrases have length at most $r$, while longer phrases use at least $r+1$ symbols. Thus $N=O(n\mathrm{/}\log n)$ uniformly over input words.

Let $\widehat{P}(L=\mathrm{\ell },U=u)=c_{\mathrm{\ell },u}\mathrm{/}N$ be the empirical law of a uniformly selected phrase. Since phrase lengths sum to $n+1$, $EL=(n+1)\mathrm{/}N$, and $U$ has at most $q^k$ values. If $\mu =EL>0$, compare the finite-support law of $L$ with the geometric weights $r_j=(\mu +1{)}^{-1}(\mu \mathrm{/}(\mu +1){)}^j$, $j\ge 0$, restricted to that finite support. The restricted weights have sum at most one, so nonnegative relative entropy [F5] gives $H_2(L)\le -E{\log }_2{r}_L=(\mu +1){\log }_2(\mu +1)-\mu {\log }_2\mu \le {\log }_2(e(\mu +1)),$ because $\ln (1+x)\le x$ for $x\ge 0$ (the derivative of $x-\ln (1+x)$ is $x\mathrm{/}(1+x)\ge 0$). The case $\mu =0$ has $H_2(L)=0$. Comparing $U$ with the uniform law on its support and using [F5] gives $H_2(U)\le k{\log }_{2}q$; [F6] gives $H_2(L,U)\le H_2(L)+H_2(U)$. Since $N=O(n\mathrm{/}\log n)$, $x\mapsto x\log ((n+1)\mathrm{/}x)$ is increasing on this range for all large $n$, so $N{H}_2(L,U)=O\text{\hspace{0.17em}⁣}\left(\frac{n\log \log n}{\log n}\right)+O\text{\hspace{0.17em}⁣}\left(\frac{kn}{\log n}\right)=o(n)$ for each fixed $k$.

The explicit code length satisfies $L_n\le N({\log }_{2}N+2{\log }_2{\log }_2(N+2)+C)+N\lceil {\log }_2(q+1)\rceil$. Since $N{\log }_{2}N={\sum }_{\mathrm{\ell },u}{c}_{\mathrm{\ell },u}{\log }_2{c}_{\mathrm{\ell },u}+N{H}_2(L,U),$ combine [F2] with step 2.1. The Ziv inequality holds for every fixed initial context, so apply it pointwise with $s=X_{-k}^{-1}$. The index redundancy and symbol fields are $o(n)$ uniformly for fixed $k$, giving $L_n\le -{\log }_2{Q}_k(X_0^{n-1}\mathrm{\#}\mid X_{-k}^{-1})+o(n)\mathrm{.}$

For the kernel in step 3.1 use the augmented alphabet $\mathcal{A}\cup \{\mathrm{\#}\}$ and $\delta =1\mathrm{/}(n+1)$. Define a probability row $p_k(\cdot \mid u)$ by the finite conditional law of $X_0$ given $X_{-k}^{-1}=u$ on positive-probability contexts and by any fixed point mass on $\mathcal{A}$ for zero-probability contexts. Set $Q_{k,n}(a\mid u)=(1-\delta )p_k(a\mid u)$ and $Q_{k,n}(\mathrm{\#}\mid u)=\delta$; after $\mathrm{\#}$ choose any stochastic row. Stationarity and the conditional-entropy definition give $E[-{\log }_2{Q}_{k,n}(X_0^{n-1}\mathrm{\#}\mid X_{-k}^{-1})]=n{H}_2(X_0\mid X_{-k}^{-1})+n{\log }_2\frac{1}{1-\delta }+{\log }_2(n+1)=n{H}_k+O(\log n),$ since $n\ln (1+1\mathrm{/}n)\le 1$. Thus [F3] and step 3.1 give ${\mathrm{lim\hspace{0.17em}sup}}_{n}E{L}_n\mathrm{/}n\le h$ after $k\to \mathrm{\infty }$.

By [F1], the LZ78 code is a prefix code, so its expected length is at least the optimal expected prefix-code length for that block. [F4] gives ${\mathrm{lim\hspace{0.17em}inf}}_{n}E{L}_n\mathrm{/}n\ge h$. Together with step 4.1 this proves convergence to $h$. The proof uses stationarity but not ergodicity.