The asymptotics of waiting times between stationary processes, allowing distortion

Given two independent realizations of the stationary processes X = Xₙ;n ≥ 1 and Y = Yₙ;n ≥ 1, our main quantity of interest is the waiting time Wₙ(D) until a D-close version of the initial string (X₁, X₂,, Xₙ) first appears as a contiguous substring in (Y₁, Y₂, Y₃,), where closeness is measured with respect to some "average distortion" criterion. We study the asymptotics of Wₙ(D) for large n under various mixing conditions on X and Y. We first prove a strong approximation theorem between ₙ(D) and the logarithm of the probability of a D-ball around (X₁, X₂,, Xₙ). 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⁻¹ log Wₙ(D) converges almost surely to a constant R determined byan explicit variational problem; (ii) [log Wₙ(D) - R], properly normalized, satisfies a central limit theorem, a law of the iterated logarithm and, more generally, an almost sure invariance principle.