More on recurrence and waiting times

Let X=Xn:n=1,2,. be a discrete valued stationary ergodic process distributed according to probability P. Let Zn1=Z1,Z2,.,Zn be an independent realization of an n-block drawn with the same probability as X. We consider the waiting time Wn defined as the first time the n-block Zn1 appears in X. There are many recent results concerning this waiting time that demonstrate asymptotic properties of this random variable. In this paper, we prove that for all n the random variable WnP(Zn1) is approximately distributed as an exponential random variable with mean 1. We use a Poisson heuristic to provide a very simple intuition for this result, which is then formalized using the Chen-Stein method. We then rederive, with remarkable brevity, most of the known asymptotic results concerning Wn and prove others as well. We further establish the surprising fact that for many sources WnP(Zn1) is exp(1) even if the probability law for Z is not the same as that of X. We also consider the d-dimensional analog of the waiting time and prove a similar result in that setting. Nearly identical results are then derived for the recurrence time Rn defined fs the first time the initial N-block Xn1 reappears in X. ge conclude by developing applications of these results to provide concise solutions to problems that stem from the analysis of the Lempel-Ziv data compression algorithm. We also consider possible applications to DNA sequence analysis.