Given two independent realizations of the stationary processes
$\mathbf{X} = {X_n;n \geq 1}$ and $\mathbf{Y} = {Y_n;n \geq 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,\dots, X_n)$ first appears as a
contiguous substring in $(Y_1, Y_2, Y_3,\dots)$, 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
$\logW_n(D)$ and the logarithm of the probability of a D-ball around
$(X_1, X_2,\dots, 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 byan 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.