On the optimality of Sliding Window Lempel-Ziv algorithm with side information

Several universal coding algorithms including LZ-78, MPM and CTW have been extended to the case with side information in the information theory literature. In this paper, we consider the side information version of sliding window Lempel-Ziv algorithm introduced by Subrahmanya and Berger. We prove the pointwise optimality of the algorithm for a class of sources with exponential rates for entropy using the asymptotic properties of recurrence times. We also study the asymptotic properties of a quantity which we call recurrence counts, introduced by Subrahmanya and Berger and prove a pointwise result regarding its convergence.