Lempel–Ziv Complexity, Empirical Entropies, and Chain Rules

We derive upper and lower bounds on the overall compression ratio of the 1978 Lempel-Ziv (LZ78) algorithm, applied independently tok-blocks of a finite individual sequence. Both bounds are given in terms of normalized empirical entropies of the given sequence. For the bounds to be tight and meaningful, the order of the empirical entropy should be small relative tokin the upper bound, but large relative tokin the lower bound. Several non-trivial conclusions arise from these bounds. One of them is a certain form of a chain rule of the Lempel-Ziv (LZ) complexity, which decomposes the joint LZ complexity of two sequences, say,xandy, into the sum of the LZ complexity ofxand the conditional LZ complexity ofygivenx(up to small terms). The price of this decomposition, however, is in changing the length of the block. Additional conclusions are discussed as well.