Given two independent realizations of the stationary processes X = {X-n;n g
reater 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 versi
on of the initial string (X-1, X-2,...,X-n) first appears as a contiguous s
ubstring in (Y-1, Y-2, Y-3,...), where closeness is measured with respect t
o some "average distortion" criterion.
We study the asymptotics of W-n(D) for large n under various mixing conditi
ons 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 ca
n, in turn, be strongly approximated by an associated random walk, and we c
onclude 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], prope
rly normalized, satisfies a central limit theorem, a law of the iterated lo
garithm and, more generally, an almost sure invariance principle.