LZ78 finite-state optimality for individual sequences

Parse $x_0^{n-1}\mathrm{\#}$ into $N$ phrases. Let $c=N-1$ be the ordinary phrases inserted into the dictionary; they are distinct by [F1]. If the terminal phrase is $w\mathrm{\#}$, its source portion $w$ is an existing dictionary word of depth at most $c$. For $r=\lfloor \frac{1}{2}{\log }_q(n+1)\rfloor$, at most ${\sum }_{j=1}^r{q}^j=O(\sqrt{n})$ distinct ordinary phrases have length at most $r$, while longer phrases consume at least $r+1$ source symbols each. Thus $c=O(n\mathrm{/}\log n)$ and $\mathrm{\mid }w\mathrm{\mid }\le c=o(n)$.

Fix an information-lossless encoder $E$ with at most $s$ states. For each of the $c$ ordinary phrases $y_i$, record its starting state $S_i$, output word $W_i$, and ending state $S_{i+1}$. The tuples $(S_i,W_i,S_{i+1})$ are distinct: equality for two different phrase strings with the same initial state would contradict injectivity in [F3]. If $J$ is uniform on the $c$ phrases and $L=\mathrm{\mid }{W}_J\mathrm{\mid }$ has mean $\mu$, then ${\log }_{2}c=H_2(S_J,W_J,S_{J+1})\le 2{\log }_{2}s+H_2(L)+EL\mathrm{.}$ The two state entropies are at most ${\log }_{2}s$, by [F4] applied to the uniform law on each state set. Conditional on $L$, there are at most $2^L$ possible binary strings, so $H_2(W_J\mid L)\le EL$.

If $\mu =0$, then $H_2(L)=0$. If $\mu >0$, compare the finite-support law of $L$ with the geometric weights $r_j=(\mu +1{)}^{-1}(\mu \mathrm{/}(\mu +1){)}^j$ restricted to that support. The reference weights sum to at most one, so nonnegative relative entropy [F4] 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$, as the derivative of $x-\ln (1+x)$ is nonnegative. The same upper bound holds when $\mu =0$. Thus $\mu \ge {\log }_{2}c-2{\log }_{2}s-{\log }_2(e(\mu +1))$. If $\mu <{\log }_{2}c$, this error is $O_s(\log \log (c+2))$; if $\mu \ge {\log }_{2}c$, the same lower bound is immediate. The $E$ output on these $c$ phrases is at most its total block output, so $c{\log }_{2}c\le L_E(x_0^{n-1})+O_s(c\log \log (c+2))\mathrm{.}$

By [F2], the LZ78 description length is at most $c{\log }_{2}c+O(c\log \log (c+2))+O(\log (c+2))$, including the terminal record. Since $c=O(n\mathrm{/}\log n)$, step 3.1 yields ${\mathrm{lim\hspace{0.17em}sup}}_n{L}_{\mathrm{L}\mathrm{Z}}(x_0^{n-1})\mathrm{/}n\le {\mathrm{lim\hspace{0.17em}sup}}_n{L}_E(x_0^{n-1})\mathrm{/}n\mathrm{.}$

The inequality holds for every fixed $s$-state information-lossless encoder. Taking the infimum over such encoders and then over $s$ proves that the LZ78 limsup rate is at most the finite-state compressibility ${\rho }_{\mathrm{F}\mathrm{S}}(x)$. This is the one-sided individual-sequence optimality claim; equality or convergence of the LZ78 rate is not asserted.