Long match patterns in random sequences
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.
- An extreme value theory for sequence matching
- The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches
- Pattern matching between two non-aligned random sequences
- On the tail probability of the longest well-matching run.
- A Poisson-type limit theorem for the number of pairs of matching sequences
- A Phase Transition for the Distribution of Matching Blocks
- scientific article; zbMATH DE number 850337 (Why is no real title available?)
This page was built for publication: Long match patterns in random sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1920138)
