Long match patterns in random sequences (Q1920138)

For fixed \(r \geq 1\), let \(M_{mn} (r)\) denote the longest run obtainable by careful alignment of two sequences \(X_1, \dots, X_m\) and \(Y_1, \dots, Y_n\) of letters, in which all but \(r\) pairs match exactly. The author considers the accuracy of the approximation of the distribution of \(M_{mn} (r)\) by a distribution derived from a Poisson approximation theorem, in the case where the elements of both sequences are independently drawn from the same distribution. For \(r \geq 1\), the rate is shown to be of order \(1/ \log (mn)\), in contrast to the rate of order almost \(n^{-1}\) which is found when \(r = 0\) [the author, Theory Probab. Appl. 39, No. 4, 593-603 (1994); translation from Teor. Veroyatn. Primen. 39, No. 4, 731-742 (1994; Zbl 0847.60016)]. The case where \(m = n\) and \(X_i = Y_i\) for all \(i\) is also investigated.