More on recurrence and waiting times

• 成果类型: Article
• 署名作者: Wyner, AJ
• 署名单位: University of Pennsylvania
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 1999
• 页码: 780-796
• 关键词: data-compression; entropy

摘要

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 probability 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 waiting 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. 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 W-n and prove others as well. We further establish the surprising fact that for 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 time the initial N-block X-1(n) reappears in X We 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.