More on recurrence and waiting times

Let X = {X-n : n = 1,2,...} be a discrete valued stationary ergodic process distributed according to probability P. Let Z(1)(n) = {Z(1), Z(2),..., Z(n )} be an independent realization of an n-block drawn Kith the same probabil ity as X. We consider the waiting time W-n defined as the first time the n- block Z(1)(n) appears in X. There are many recent results concerning this w aiting time that demonstrate asymptotic properties of this random variable. In this paper, we prove that for all n the random variable WnP(Z(1)(n)) is approximately distributed as an exponential random variable with mean 1. W e use a Poisson heuristic to provide a very simple intuition for this resul t, which is then formalized using the Chen-Stein method. We then rederive, with remarkable brevity, most of the known asymptotic results concerning W- n and prove others as well. We further establish the surprising fact that f or many sources WnP(Z(1)(n)) 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 R-n defined as the first t ime the initial N-block X-1(n) reappears in X We conclude by developing app lications of these results to provide concise solutions to problems that st em from the analysis of the Lempel-Ziv data compression algorithm. We also consider possible applications to DNA sequence analysis.