Geodesic
On the probability of existence of substrings with the same structure in a random sequence
Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 97-110.

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

An asymptotic expression (with an explicit estimate of the remainder term) is obtained for the probability that in a finite sequence of polynomial trials controlled by a Markov chain there exist substrings having the same structure.
Keywords: polynomial scheme, Markov chain, structure of substring, equivalent substrings. 
@article{DM_2016_28_3_a6,
     author = {V. G. Mikhailov},
     title = {On the probability of existence of substrings with the same structure in a random sequence},
     journal = {Diskretnaya Matematika},
     pages = {97--110},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_3_a6/}
}
TY  - JOUR
AU  - V. G. Mikhailov
TI  - On the probability of existence of substrings with the same structure in a random sequence
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 97
EP  - 110
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_3_a6/
LA  - ru
ID  - DM_2016_28_3_a6
ER  - 
%0 Journal Article
%A V. G. Mikhailov
%T On the probability of existence of substrings with the same structure in a random sequence
%J Diskretnaya Matematika
%D 2016
%P 97-110
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_3_a6/
%G ru
%F DM_2016_28_3_a6
V. G. Mikhailov. On the probability of existence of substrings with the same structure in a random sequence. Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 97-110. http://geodesic.mathdoc.fr/item/DM_2016_28_3_a6/

[1] Buravlev S. M., “Matchings up to permutations in sequences of independent trials”, Discrete Math. Appl., 9:1 (1999), 53–78 | DOI | DOI | MR | Zbl

[2] Mikhailov V. G., Shoitov A. M., “Structural equivalence of $s$-tuples in random discrete sequences”, Discrete Math. Appl., 13:6 (2003), 541–568 | DOI | DOI | MR | Zbl

[3] Mikhailov V. G., “On the asymptotic behaviour of the probability of existence of equivalent tuples with nontrivial structure in a random sequence”, Discrete Math. Appl., 18:6 (2008), 563–568 | DOI | DOI | MR | Zbl

[4] Mikhailov V. G., Shoitov A. M., “O chislakh mnozhestv ekvivalentnykh tsepochek v posledovatelnosti nezavisimykh sluchainykh velichin”, Matematicheskie voprosy kriptografii, 4:1 (2013), 77–86

[5] Elliott R. J., Aggoun L., Moore J. B. Hidden Markov Models, Springer-Verlag, N.-Y., 1995 | MR | Zbl

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

[7] Chryssaphinou O., Vaggelatou E., “Compound Poisson approximation for multiple runs in a Markov chain”, Ann. Inst. Statist. Math., 54:2 (2002), 411–424 | DOI | MR | Zbl

[8] Mikhailov V. G., Shoitov A. M., “On repetitions of long tuples in a Markov chain”, Discrete Math. Appl., 25:5 (2015), 295–303 | DOI | DOI | MR

[9] Mikhailov V. G., Shoitov A. M., “Mnogokratnye povtoreniya dlinnykh tsepochek v tsepi Markova”, Matematicheskie voprosy kriptografii, 6:3 (2015), 117–133

[10] Mikhailov V. G., “Estimates of accuracy of the Poisson approximation for the distribution of number of runs of long string repetitions in a Markov chain”, Discrete Math. Appl., 26:2 (2016), 105–113 | DOI | DOI | MR