A Poisson-Type Limit Theorem for the Number of Pairs of Matching Sequences

V. G. Mikhailov

Teoriâ veroâtnostej i ee primeneniâ, Tome 53 (2008) no. 1, pp. 59-71

Résumé

Two sequences $X_1,\dots,X_m$ and $Y_1,\dots,Y_n$ are considered constituted by independent identically distributed random variables within each of the sequences taking on values in the set $\{1,2,\dots\}$. We study the distribution of the number $N_d$ of such pairs of $s$-patterns $(\overline X_i,\overline Y_j)$, where $\overline X_i=(X_i,\dots,X_{i+s-1})$, $\overline Y_j=(Y_j,\dots,Y_{j+s-1})$, in which the $s$-patterns $\overline X_i$ and $\overline Y_j$ differ by a relatively small number of elements $d$. It is shown that if ${m,n,s\to\infty}$, $d=o(s/\log s),$ and the distributions of the elements of the sequences vary in such a way that the probability $P\{X_i=Y_j\}$ and $EN_d$ converge to some limiting values, then the distribution of $N_d$ converges to a compound Poisson distribution. The value of the parameter $d$ plays a role only to provide, passing to the limit, the needed rate of the parameters involved and has no influence on the form of the limit distribution. This limit distribution has the same form as that for the number of pairs $(\overline X_i,\overline Y_j)$, in which $\overline X_i=\overline Y_j$.

Détail

Keywords: $s$-patterns, pattern matching, mismatches of patterns, compound Poisson distribution, Chen-Stein method.
Mots-clés : Poisson limit theorem