The asymptotics of waiting times between stationary processes, allowing distortion

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.