On the distribution of recurrence times and the exact asymptotics of Lempel-Ziv coding
Ioannis Kontoyiannis · 2002
; abstract apeared in Proceedings of the 1997 IEEE International Symposium on Information Theory, Ulm, Germany, June-July 1997 Abstract -- Let X = fXn ; n 2 Zg be a finitealphabet, stationary ergodic source distributed according to P and let x = (: : : ; x \\Gamma1 ; x 0 ; x 1 ; : : :) denote a realization from X. We investigate the asymptotic behavior of the recurrence time Rn defined as the first time that the initial n-block x n 1 = (x 1 ; x 2 ; : : : ; xn ) recurs in the past of the realization x. We provide a natural probabilistic framework for deducing the exact asymptotic behavior of Rn , and we use our results to extract precise information about the behavior of the pointwise redundancy of an idealized version of the Lempel-Ziv code. As a byproduct of our analysis we get unified simple proofs for several recent results, that were previously established using involved methods from ergodic theory, the theory of Poisson approximation and the analysis of random trees. I. Int...