On Certain Pathwise Properties of the Sliding-Window Lempel–Ziv Algorithm

We derive several almost-sure results related to the sliding-window Lempel-Ziv (SWLZ) algorithm. A principal result is a path-wise lower bound to the redundancy equal to 1/2hlog₂log ₂n_w/log₂n_w in the main term, where n_w is the sliding window size. This bound is off by a factor of two from the main term in the lower bound of A. J. Wyner and the work of Yang and Kieffer, which hold in the expected sense for the fixed-database Lempel-Ziv algorithm (FDLZ). Another aspect of the present work studies the asymptotic behavior of the ratio of the number of phrases to the length of the parsed string for any finite sliding window size; in here we exploit the theory of asymptotic mean stationary processes of Gray and Kieffer and some results of Kieffer and Rahe. In all cases it is assumed that the source is stationary and that in the most restrictive case it is an irreducible and aperiodic Markov chain; some of the results hold for sources that have exponential rates for entropy and more generally for the ergodic setting