The asymptotics of waiting times between stationary processes, allowing distortion

• 成果类型: Article
• 署名作者: Dembo, A; Kontoyiannis, I
• 署名单位: Stanford University; Purdue University System; Purdue University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 1999
• 页码: 413-429
• 关键词: data-compression; SEQUENCES; algorithm

摘要

Given two independent realizations of the stationary processes X = {X-n;n greater than or equal to 1} and Y = {Y-n; n greater than or equal to 1}, our main quantity of interest is the waiting time W-n(D) until a D-close version of the initial string (X-1, X-2,...,X-n) first appears as a contiguous substring in (Y-1, Y-2, Y-3,...), where closeness is measured with respect to some average distortion criterion. We study the asymptotics of W-n(D) for large n under various mixing conditions on X and Y. We first prove a strong approximation theorem between log W-n(D) and the logarithm of the probability of a D-ball around (X-1, X-2,..., X-n). Using large deviations techniques, we show that this probability can, in turn, be strongly approximated by an associated random walk, and we conclude that: (i) n(-1) log W-n(D) converges almost surely to a constant R determined by an explicit variational problem; (ii) [log W-n(D) - R], properly normalized, satisfies a central limit theorem, a law of the iterated logarithm and, more generally, an almost sure invariance principle.