The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches. (English) Zbl 0688.62019

Summary: Consider two random sequences \(X_ 1....X_ n\) and \(Y_ 1...Y_ n\) of i.i.d. letters in which the probability that two distinct letters match is \(p>0\). For each value \(\alpha\) between p and 1, the length of the longest contiguous matching between the two sequences, requiring only a proportion \(\alpha\) of corresponding letters to match, satisfies a strong law analogous to the Erdős-Rényi law for coin tossing. The same law applies to matching between two nonoverlapping regions within a single sequence \(X_ 1...X_ n\), and a strong law with a smaller constant applies to matching between two overlapping regions within that single sequence. The method here also works to obtain the strong law for matching between multidimensional arrays, between two Markov chains and for the situation in which a given proportion of mismatches is required.


62E20 Asymptotic distribution theory in statistics
60F15 Strong limit theorems
62P10 Applications of statistics to biology and medical sciences; meta analysis
Full Text: DOI