Geodesic
Structural equivalence of $s$-tuples in random discrete sequences
Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 7-34.

Voir la notice de l'article provenant de la source Math-Net.Ru

Recently there appeared a significant number of papers investigating structural properties of random discrete sequences. They provide a large group of results on structurally equivalent intervals in such sequences. The goal of the present paper is to give a survey of the problems and the known results in this interesting area of discrete probability theory. This research was supported by the Russian Foundation for Basic Research, grant 02–01–00266, by the grant 1758.2003.1 of the State support of the leading scientific schools of the Russian Federation, and by the grant 2831.2003.09 of the State support of young Russian scientists. 
@article{DM_2003_15_4_a1,
     author = {V. G. Mikhailov and A. M. Shoitov},
     title = {Structural equivalence of $s$-tuples in random discrete sequences},
     journal = {Diskretnaya Matematika},
     pages = {7--34},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_4_a1/}
}
TY  - JOUR
AU  - V. G. Mikhailov
AU  - A. M. Shoitov
TI  - Structural equivalence of $s$-tuples in random discrete sequences
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 7
EP  - 34
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_4_a1/
LA  - ru
ID  - DM_2003_15_4_a1
ER  - 
%0 Journal Article
%A V. G. Mikhailov
%A A. M. Shoitov
%T Structural equivalence of $s$-tuples in random discrete sequences
%J Diskretnaya Matematika
%D 2003
%P 7-34
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2003_15_4_a1/
%G ru
%F DM_2003_15_4_a1
V. G. Mikhailov; A. M. Shoitov. Structural equivalence of $s$-tuples in random discrete sequences. Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 7-34. http://geodesic.mathdoc.fr/item/DM_2003_15_4_a1/

[1] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P., Sluchainye razmescheniya, Nauka, Moskva, 1976 | MR | Zbl

[2] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, Moskva, 1982 | MR | Zbl

[3] Ivanov V. A., Ivchenko G. I., Medvedev Yu. I., “Diskretnye zadachi teorii veroyatnostei”, Itogi nauki i tekhniki. Ser. Teoriya veroyatnostei. Matematicheskaya statistika. Teoreticheskaya kibernetika, 22, 1984, 3–60 | MR | Zbl

[4] Buravlev S. M., “Puassonovskoe predelnoe raspredelenie chisla otrezkov, svyazannykh podstanovkami iz simmetricheskoi gruppy, v posledovatelnosti nezavisimykh ravnoveroyatnykh ispytanii”, Vtoraya Vserossiiskaya shkola-kollokvium po stokhasticheskim metodam. Tezisy dokladov, TVP, Moskva, 1995, 28–30

[5] Buravlev S. M., “Nekotorye algoritmy podscheta statistik, zavisyaschikh ot chisla par otrezkov posledovatelnosti, svyazannykh podstanovkami”, Obozrenie prikladnoi i promyshlennoi matematiki, 4:3 (1997), 331–333

[6] Buravlev S. M., “Predelnye teoremy dlya sluchainykh velichin ot chisla par otrezkov, svyazannykh podstanovkami iz latinskogo pryamougolnika”, Tretya Vserossiiskaya shkola-kollokvium po stokhasticheskim metodam. Tezisy dokladov, TVP, Moskva, 1996, 37–40

[7] Buravlev S. M., “Lokalnaya asimptoticheskaya normalnost chisla par otrezkov posledovatelnosti, svyazannykh podstanovkami iz latinskogo pryamougolnika”, Obozrenie prikladnoi i promyshlennoi matematiki, 5:2 (1998), 205–207

[8] Buravlev S. M., “Utochnenie odnogo predelnogo raspredeleniya”, Obozrenie prikladnoi i promyshlennoi matematiki, 6:1 (1999), 127–128 | MR

[9] Buravlev S. M., “Povtoreniya s tochnostyu do perestanovok v posledovatelnosti nezavisimykh ispytanii”, Diskretnaya matematika, 11:1 (1999), 53–75 | MR | Zbl

[10] Buravlev S. M., “Povtoreniya s tochnostyu do perestanovok, obrazuyuschikh latinskii pryamougolnik”, Diskretnaya matematika, 12:1 (2000), 24–46 | MR | Zbl

[11] Gusev V. D., Nemytikova L. A., “Slozhnostnye kharakteristiki geneticheskikh tekstov”, Trudy 4-i Vserossiiskoi konf. “Raspoznavanie obrazov i analiz izobrazhenii”, ch. 1, Novosibirsk, 1998, 83–87

[12] Gusev V. D., Nemytikova L. A., “Uchet proyavlenii povtornosti, simmetrii i izomorfizma v simvolnykh posledovatelnostyakh: algoritmicheskie aspekty”, Vychislitelnye sistemy, 167 (2001), 11–33 | MR | Zbl

[13] Zubkov A. M., “Neravenstva dlya veroyatnostei perekhodov s zaprescheniyami i ikh primeneniya”, Matem. sb., 109 (151):4 (8) (1979), 491–532 | MR | Zbl

[14] Zubkov A. M., “Otsenki dlya summ konechno-zavisimykh indikatorov i dlya momenta pervogo nastupleniya redkogo sobytiya”, Trudy MIAN, 177, 1986, 33–46 | MR | Zbl

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

[16] Zubkov A. M., Mikhailov V. G., “Otsenka tochnosti puassonovskoi approksimatsii v zadache o razmeschenii chastits po yacheikam”, Teoriya veroyatnostei i ee primeneniya, 23:4 (1978), 819–824 | MR | Zbl

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

[18] Zubkov A. M., Popov N. N., “Otnoshenie chastichnogo poryadka, porozhdennoe raspredeleniyami chisla zanyatykh yacheek”, Matem. zametki, 32:1 (1982), 97–102 | MR | Zbl

[19] Kolchin V. F., Chistyakov V. P., “Predelnye raspredeleniya chisla nepoyavivshikhsya $s$-tsepochek v polinomialnoi skheme”, Teoriya veroyatnostei i ee primeneniya, 19:4 (1974), 855–864 | Zbl

[20] Medvedev Yu. I., “Nekotorye teoremy ob asimptoticheskom raspredelenii statistiki $\chi^2$”, Dokl. AN SSSR, 192:5 (1970), 987–989 | MR | Zbl

[21] Mikhailov V. G., “Predelnye raspredeleniya sluchainykh velichin, svyazannykh s mnogokratnymi dlinnymi povtoreniyami v posledovatelnosti nezavisimykh ispytanii”, Teoriya veroyatnostei i ee primeneniya, 19:1 (1974), 182–187

[22] Mikhailov V. G., “Tsentralnaya predelnaya teorema dlya chisla nepolnykh dlinnykh povtorenii”, Teoriya veroyatnostei i ee primeneniya, 20:4 (1975), 880–884 | MR

[23] Mikhailov V. ,G., “Tsentralnaya predelnaya teorema dlya neodnorodnykh $U$-statistik ot konechno zavisimykh sluchainykh velichin”, Matem. sb., 98 (140):4 (12) (1975), 624–634 | MR

[24] Mikhailov V. G., “Asimptoticheskaya normalnost v skheme konechno-zavisimogo razmescheniya chastits po yacheikam”, Matem. sb., 119:4 (1982), 509–520 | MR

[25] Mikhailov V. G., “Asimptoticheskaya normalnost razdelimykh statistik ot chastot $m$-tsepochek”, Diskretnaya matematika, 1:4 (1989), 92–103

[26] Mikhailov V. G., “Yavnye otsenki v predelnykh teoremakh dlya summ sluchainykh indikatorov”, Obozrenie prikladnoi i promyshlennoi matematiki, 1:4 (1994), 580–617

[27] Mikhailov V. G., “Otsenka tochnosti slozhnoi puassonovskoi approksimatsii po metodu Steina–Chena”, Obozrenie prikladnoi i promyshlennoi matematiki, 3:4 (1996), 530–548 | MR

[28] Mikhailov V. G., “Nekotorye neravenstva dlya funktsii raspredeleniya chisla nepoyavivshikhsya $s$-tsepochek”, Trudy po diskretnoi matematike, 1, 1997, 221–226

[29] Mikhailov V. G., “Otsenka tochnosti slozhnoi puassonovskoi approksimatsii dlya raspredeleniya chisla sovpadayuschikh tsepochek”, Teoriya veroyatnostei i ee primeneniya, 46:4 (2001), 713–723

[30] Mikhailov V. G., “Neravenstva dlya srednego chisla povtorenii $m$-tsepochek i dlya srednego chisla nepoyavivshikhsya $m$-tsepochek iz zadannogo klassa”, Trudy po diskretnoi matematike, 3, 2000, 147–154

[31] Mikhailov V. G., “Ob asimptoticheskikh svoistvakh raspredeleniya chisla par $H$-svyazannykh tsepochek”, Diskretnaya matematika, 14:3 (2002), 122–129 | Zbl

[32] Timashev A. N., “O veroyatnosti sovpadeniya vektorov chastot iskhodov nezavisimykh polinomialnykh skhem”, Tretya Vserossiiskaya shkola-kollokvium po stokhasticheskim metodam. Tezisy dokladov, TVP, Moskva, 1996, 156–157

[33] Tikhomirova M. I., “Ob asimptoticheskoi normalnosti chisla nepoyavivshikhsya $s$-tsepochek”, Diskretnaya matematika, 4:2 (1992), 122–129 | MR

[34] Tikhomirova M. I., Chistyakov V. P., “Ob asimptotike momentov chisla nepoyavivshikhsya $s$-tsepochek”, Diskretnaya matematika, 9:1 (1997), 12–29 | MR | Zbl

[35] Tikhomirova M. I., Chistyakov V. P., “O statisticheskikh kriteriyakh otsutstvuyuschikh $s$-gramm”, Trudy po diskretnoi matematike, 1 (1997), 265–278 | MR | Zbl

[36] Shoitov A. M., “Predelnye raspredeleniya chisla naborov $H$-ekvivalentnykh otrezkov v ravnoveroyatnoi polinomialnoi skheme serii”, Diskretnaya matematika, 14:1 (2002), 82–98 | MR | Zbl

[37] Shoitov A. M., “Povtoreniya znachenii funktsii ot otrezkov posledovatelnosti nezavisimykh ispytanii”, Diskretnaya matematika, 12:3 (2000), 49–59 | MR | Zbl

[38] Shoitov A. M., “Predelnye raspredeleniya chisla naborov $H$-ekvivalentnykh otrezkov v posledovatelnosti nezavisimykh ispytanii”, Obozrenie prikladnoi i promyshlennoi matematiki, 6:1 (1999), 218–220

[39] Shoitov A. M., “Svyaz otrezkov otnosheniem $H$-ekvivalentnosti v skheme serii”, Obozrenie prikladnoi i promyshlennoi matematiki, 6:1 (1999), 220–221

[40] Shoitov A. M., “Verkhnyaya otsenka rasstoyaniya po variatsii mezhdu raspredeleniem sluchainoi velichiny, ravnoi chislu naborov $H$-ekvivalentnykh otrezkov v ravnoveroyatnoi skheme serii, i raspredeleniem Puassona”, Obozrenie prikladnoi i promyshlennoi matematiki, 7:2 (2000), 546–547

[41] Shoitov A. M., “O skorosti skhodimosti chisla naborov $H$-ekvivalentnykh otrezkov v ravnoveroyatnoi skheme serii k slozhnomu raspredeleniyu Puassona”, Obozrenie prikladnoi i promyshlennoi matematiki, 8:1 (2001), 381–381

[42] Shoitov A. M., “Slozhnoe raspredelenie Puassona chisla naborov $H$-ekvivalentnykh otrezkov v posledovatelnosti nezavisimykh ispytanii”, Obozrenie prikladnoi i promyshlennoi matematiki, 8:2 (2001), 816–816

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

[44] Arratia R., Waterman M. S., “Critical phenomena in sequence matching”, Ann. Probab., 13:4 (1985), 1236–1249 | DOI | MR | Zbl

[45] 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

[46] Barbour A. D., Holst L., Janson S., Poisson approximation, Oxford University Press, Oxford, 1992 | MR | Zbl

[47] Benczur A., Katai I., “On the number of occurrences of sequence patterns”, Acta Math. Hung., 47:3-4 (1986), 371–382 | DOI | MR | Zbl

[48] Biggins J. D., “A note on repeated sequences in Markov chains”, Adv. Appl. Probab., 19:3 (1987), 739–742 | DOI | MR | Zbl

[49] Chrysaphinou O., Papastavridis S., “A limit theorem on the number of overlapping appearances of a pattern in a sequence of independent trials”, Probab. Theory Relat. Fields, 79 (1988), 129–143 | DOI | MR | Zbl

[50] Chrysaphinou O., Papastavridis S., “A limit theorem on the number of non-overlapping occurrences of a pattern in a sequence of independent trials”, J. Appl. Probab., 25:2 (1988), 428–431 | DOI | MR

[51] Chrysaphinou O., Papastavridis S., “The occurrence of sequence patterns in repeated dependent experiments”, Teoriya veroyatnostei i ee primeneniya, 35:1 (1990), 167–173 | MR

[52] Dembo A., Karlin S., Zeitouni O., “Critical phenomena for sequence matching with scoring”, Ann. Probab., 22:4 (1994), 1993–2021 | DOI | MR | Zbl

[53] Dembo A., Karlin S., Zeitouni O., “Limit distribution of maximal non-aligned two-sequence segmental score”, Ann. Probab., 22:4 (1994), 2022–2039 | DOI | MR | Zbl

[54] Gordon L., Schilling M. F., Waterman M., “An extreme value theory for sequence matching”, Probab. Theory Relat. Fields, 72 (1986), 279–287 | DOI | MR | Zbl

[55] Karlin S., Ost F., “Count of long aligned word matches among random letter sequences”, Adv. Appl. Probab., 19:2 (1987), 293–351 | DOI | MR | Zbl

[56] Karlin S., Ost F., “Maximal length of common words among random letter sequences”, Ann. Probab., 16:3 (1988), 535–563 | DOI | MR | Zbl

[57] Karnin E. D., “The first repetition of a pattern in a symmetric Bernoulli sequence”, J. Appl. Probab., 20 (1983), 413–418 | DOI | MR | Zbl

[58] Lempel A., Ziv J., “On the complexity of finite sequences”, IEEE Trans. Inf. Theory, 22:1 (1976), 75–81 | DOI | MR | Zbl

[59] Rukhin A. L., “Distribution of the number of words with a prescribed frequency and tests of randomness”, Adv. Appl. Prob., 34 (2002), 775–797 | DOI | MR | Zbl