Average redundancy rate of the Lempel-Ziv code

It was conjectured that the average redundancy rate, r_n, for the Lempel-Ziv code (1978) is Θ(loglog n/log n) where n is the length of the database sequence. However, it was also known that for infinitely many n the redundancy r_n is bounded from the below by 2/log n. We settle the above conjecture in the negative by proving that for a memoryless source the average redundancy rate attains asymptotically Er_n=(A+δ(n))/log n+O(loglog n/log²n) where A is an explicitly given constant that depends on the source characteristics, and δ(x) is a fluctuating function. This result is a consequence of the established second-order properties for the number of phrases in the Lempel-Ziv algorithm. We also derive the leading term for the kth moment of the number of phrases. Finally, we discuss generalized Lempel-Ziv codes for which the average redundancy rates are computed and compared with the original Lempel-Ziv code