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

## Abstract

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 |
---|---|

Subjects: | UNSPECIFIED |

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 |