On compound Poisson approximation for sequence matching (Q2711618)

Let \(A_1,\dots, A_m\) and \(B_1,\dots, B_n\) each be independent and identically distributed sequences of random variables from distributions \(\mu\) and \(\nu\), respectively, over a finite alphabet. The paper considers the distribution of the number \(W\) of pairs \(i\), \(j\) such that \(A_{i+l}= B_{j+l}\) for all but at most \(r\) values of \(l\), \(0\leq l\leq k-1\), for \(k\) suitably large; the motivation is to approximate the null hypothesis distributions of statistics measuring the degree of local similarity between two molecular sequences, where some mismatches are allowed. The Stein-Chen method is used to establish the accuracy of a compound Poisson approximation to the distribution of \(W\) with respect to the total variation distance; the distance between the two is shown to be asymptotically negligible in a wide variety of settings.