Geodesic
A Poisson-Type Limit Theorem for the Number of Pairs of Matching Sequences
Teoriâ veroâtnostej i ee primeneniâ, Tome 53 (2008) no. 1, pp. 59-71
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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$.
Keywords: $s$-patterns, pattern matching, mismatches of patterns, compound Poisson distribution, Chen-Stein method.
Mots-clés : Poisson limit theorem 
@article{TVP_2008_53_1_a3,
     author = {V. G. Mikhailov},
     title = {A {Poisson-Type} {Limit} {Theorem} for the {Number} of {Pairs} of {Matching} {Sequences}},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {59--71},
     year = {2008},
     volume = {53},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2008_53_1_a3/}
}
TY  - JOUR
AU  - V. G. Mikhailov
TI  - A Poisson-Type Limit Theorem for the Number of Pairs of Matching Sequences
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2008
SP  - 59
EP  - 71
VL  - 53
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TVP_2008_53_1_a3/
LA  - ru
ID  - TVP_2008_53_1_a3
ER  - 
%0 Journal Article
%A V. G. Mikhailov
%T A Poisson-Type Limit Theorem for the Number of Pairs of Matching Sequences
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2008
%P 59-71
%V 53
%N 1
%U http://geodesic.mathdoc.fr/item/TVP_2008_53_1_a3/
%G ru
%F TVP_2008_53_1_a3
V. G. Mikhailov. A Poisson-Type Limit Theorem for the Number of Pairs of Matching Sequences. Teoriâ veroâtnostej i ee primeneniâ, Tome 53 (2008) no. 1, pp. 59-71. http://geodesic.mathdoc.fr/item/TVP_2008_53_1_a3/

[1] Arratia R., Gordon L., Waterman M. S., “An extreme value theory for sequence matching”, Ann. Statist., 14:3 (1986), 971–993 | DOI | MR | Zbl

[2] Arratia R., Waterman M. S., “The Erdös–Rényi strong law for pattern matching with a given proportion of mismatches”, Ann. Probab., 17:3 (1989), 1152–1169 | DOI | MR | Zbl

[3] Arratia R., Gordon L., Waterman M. S., “The Erdös–Rényi law in distribution, for coin tossing and sequence matching”, Ann. Statist., 18:2 (1990), 539–570 | DOI | MR | Zbl

[4] Novak S. Yu., “Puassonova approksimatsiya chisla dlinnykh “povtorov” v sluchainykh posledovatelnostyakh”, Teoriya veroyatn. i ee primen., 39:4 (1994), 731–742 ; 40:3 (1995), 700 | MR | MR | Zbl

[5] Novak S. Yu., “Long match patterns in random sequences”, Siberian Adv. Math., 5:3 (1995), 128–140 | MR | Zbl

[6] Mikhailov V. G., “Otsenka tochnosti slozhnoi puassonovskoi approksimatsii dlya raspredeleniya chisla sovpadayuschikh tsepochek”, Teoriya veroyatn. i ee primen., 46:4 (2001), 713–723 | MR

[7] Mikhailov V. G., “Predelnye teoremy puassonovskogo tipa dlya chisla nepolnykh sovpadenii $s$-tsepochek”, Teoriya veroyatn. i ee primen., 47:2 (2002), 350–357

[8] Zubkov A. M., Mikhailov V. G., “Predelnye raspredeleniya sluchainykh velichin, svyazannykh s dlinnymi povtoreniyami v posledovatelnosti nezavisimykh ispytanii”, Teoriya veroyatn. i ee primen., 19:1 (1974), 173–181 | MR | Zbl

[9] Zubkov A. M., Mikhailov V. G., “O povtoreniyakh $s$-tsepochek v posledovatelnosti nezavisimykh velichin”, Teoriya veroyatn. i ee primen., 24:2 (1979), 267–279 | MR | Zbl

[10] Roos M., “Stein's method for compound Poisson approximation: the local approach”, Ann. Appl. Probab., 4 (1994), 1177–1187 | DOI | MR | Zbl

[11] Månsson M., “On compound Poisson approximation for sequence matching”, Combin. Probab. Comp., 9:6 (2000), 529–548 | DOI | MR

[12] Barbour A. D., Holst L., Janson S., Poisson Approximation, Oxford Univ. Press, New York, 1992, 277 pp. | MR | Zbl