Distinct-phrase count and Ziv inequality

For each phrase start $i$, let $u_i\in {\mathcal{B}}^k$ be its preceding context, using $s$ for the initial boundary; write ${\mathrm{\ell }}_i=\mathrm{\mid }{y}_i\mathrm{\mid }$. For each pair $(\mathrm{\ell },u)$ let $c_{\mathrm{\ell },u}$ count phrases of that length and context. Markov factorization gives $Q(y_0^{m-1}\mid s)={\prod }_{i}Q(y_i\mid u_i)$.

Group the logarithm by $(\mathrm{\ell },u)$ with $c_{\mathrm{\ell },u}>0$; groups of count zero contribute zero. Concavity of ${\log }_2$ gives ${\sum }_{i:({\mathrm{\ell }}_i,u_i)=(\mathrm{\ell },u)}{\log }_{2}Q(y_i\mid u)\le c_{\mathrm{\ell },u}{\log }_2(\frac{1}{c_{\mathrm{\ell },u}}{\sum }_{i}Q(y_i\mid u))\mathrm{.}$ Within this group the phrase strings are distinct by the given parsing hypothesis (supplied by [F1] for the LZ78 specialization), so their conditional probabilities sum to at most one; therefore the group contribution is at most $-c_{\mathrm{\ell },u}{\log }_2{c}_{\mathrm{\ell },u}$.

Summing all groups and negating yields the Ziv inequality $-{\log }_{2}Q(y_0^{m-1}\mid s)\ge {\sum }_{\mathrm{\ell },u}{c}_{\mathrm{\ell },u}{\log }_2{c}_{\mathrm{\ell },u}\mathrm{.}$ For the augmented LZ78 specialization, the terminal phrase has the unique symbol $\mathrm{\#}$ and cannot equal any ordinary phrase; [F1] supplies distinctness of the remaining phrases. For the empty parsing, both sides are zero. Zero kernel probabilities on an observed word make the left side $+\mathrm{\infty }$, and the inequality is then immediate.