The asymptotics of waiting times between stationary processes, allowing distortion (Q1305418)

Let \(X= \{X_n\}\) and \(Y= \{Y_n\}\) be independent stationary processes with distributions \(P\) and \(Q\), respectively. Let \((x_1,x_2,\dots)\), \((y_1,y_2,\dots)\) be realizations of \(X\) and \(Y\), respectively. For \(D\geq 0\) and a measurable nonnegative function \(\rho(\cdot,\cdot)\) define \[ W_n(D)= \inf\Biggl\{k\geq 1: \sum^n_{i=1} \rho(x_i, y_{i+k-1})\leq nD\Biggr\} \] which is the waiting time until a \(D\)-close version \((x_1,\dots, x_n)\) first appears in \(y\). Assuming various mixing conditions on \(X\) and \(Y\) it is proved that: (i) \(\log W_n(D)+ \log Q\left((y_1,\dots, y_n): \sum^n_{i= 1}\rho(X_i, y_i)\leq nD\right)= o(\sqrt n)\), \(P\times Q\)-a.s., (ii) there exist a constant \(R\) determined by an explicit variational problem and a sequence \(\{\overline\Lambda_{X_i}(\lambda)\}\) induced by \((X_i)\) such that \(\log W_n(D)- nR+ \sum^n_{i=1}\overline\Lambda_{X_i}(\lambda)= o(\sqrt n)\), \(P\times Q\)-a.s. Hence, \((\log W_n(D)- nR)\), properly normalized, satisfies a central limit theorem, a law of the iterated logarithm and an almost sure invariance principle. Applications of the results to data compression and DNA sequence analysis are outlined.