The asymptotics of waiting times between stationary processes, allowing distortion

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 \logWn(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.1logWn(D) converges almost surely to a constant R determined byan explicit variational problem; (ii) [logWn(D).R], properly normalized, satisfies a central limit theorem, a law of the iterated logarithm and, more generally, an almost sure invariance principle.