CUED Publications database

The asymptotics of waiting times between stationary processes, allowing distortion

Dembo, A and Kontoyiannis, I (1999) The asymptotics of waiting times between stationary processes, allowing distortion. Annals of Applied Probability, 9. pp. 413-429. ISSN 1050-5164

Full text not available from this repository.


Given two independent realizations of the stationary processes X = {Xn; n ≥ 1} and Y = {Yn; n ≥ 1}, our main quantity of interest is the waiting time Wn(D) until a D-close version of the initial string (X1, X2, . . . , Xn) first appears as a contiguous substring in (Y1, Y2, Y3, . . .), where closeness is measured with respect to some "average distortion" criterion. We study the asymptotics of Wn(D) for large n under various mixing conditions on X and Y. We first prove a strong approximation theorem between log Wn(D) and the logarithm of the probability of a D-ball around (X1, X2, . . . , Xn). 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 Wn(D) converges almost surely to a constant R determined by an explicit variational problem; (ii) [log Wn(D) - R], properly normalized, satisfies a central limit theorem, a law of the iterated logarithm and, more generally, an almost sure invariance principle.

Item Type: Article
Divisions: Div F > Signal Processing and Communications
Depositing User: Cron Job
Date Deposited: 08 Jan 2018 20:12
Last Modified: 01 Oct 2020 03:16
DOI: 10.1214/aoap/1029962749