An Erdős-Rényi law with shifts (Q1071378)

Consider two sequences of ''letters'' \(X_ 1,X_ 2,...\); \(Y_ 1,Y_ 2,..\)., where all the random variables are assumed to be independent and identically distributed. Motivated by the comparison of DNA sequences, the authors are interested in the length of the longest matching consecutive subsequence of \(X_ 1,...,X_ n\) and \(Y_ 1,...,Y_ n\), respectively, i.e. \(M_ n=\max \{m:X_{i+k}=Y_{j+k}\) for \(k=1,...,m\), for some \(0\leq i,j\leq n-m\}\), \(R_ n=\max \{m:X_{i+k}=Y_{i+k}\) for \(k=1,...,m\), for some \(0\leq i\leq n-m\}\), allowing ''shifts'' in the first case and no shifts else. From the Erdős-Rényi law of large numbers for runs in coin tosses, it can be derived that P(\(\lim_{n\to \infty}R_ n/\log_{1/p} n=1)=1\), where \(p=P(X_ 1=Y_ 1)\in (0,1)\). For matching with shifts, the authors analogously prove that P(\(\lim_{n\to \infty}M_ n/\log_{1/p} n=2)\), together with certain convergence rate statements. The case of Markov chains is also treated. The paper above of Darling and Waterman, deals with sequences of letters indexed by points of the integer lattice \({\mathbb{Z}}^ d\). Analogues of the above mentioned limit theorems (without rates) are established for the volume of the largest matching cubes and rectangles in \(\{1,...,n\}^ d\), with and without shifts. Certain algorithms for finding largest squares and rectangles in the case \(d=2\) are also discussed.