Geodesic
Asymptotic normality of number of multiple coincidences of chains in complete $q$-ary trees and forests with randomly marked vertices
Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 8-11.

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

We consider complete $q$-ary trees of height $H$ with vertices marked by random independent marks taking values from some the set $\{1,2,\ldots, N\}$. The object of our research is the number of tuples of $r\ge 2$ paths having the same length $s$ and identical sequences of vertex marks. We propose a theorem on sufficient conditions of asymptotic normality of considered random values for the case when height of the tree tends to infinity. We also investigate repetitions of chains in forest of trees and suppose that there are $r$ trees which may have different heights $H_1, \ldots,H_r$ and vertices of these trees are marked in the same way. We consider the number of tuples of $r$ paths of the same length $s$ and suppose that a tuple includes one path from each tree. For such numbers of tuples, we also propose similar theorem on sufficient conditions of asymptotic normality.
Keywords: marked trees, chains of marks, chains on a tree, repetitions of chains, conditions of asymptotic normality. 
@article{PDMA_2022_15_a1,
     author = {V. G. Mikhailov and V. I. Kruglov},
     title = {Asymptotic normality of number of multiple coincidences of chains in complete $q$-ary trees and forests with randomly marked vertices},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {8--11},
     publisher = {mathdoc},
     number = {15},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2022_15_a1/}
}
TY  - JOUR
AU  - V. G. Mikhailov
AU  - V. I. Kruglov
TI  - Asymptotic normality of number of multiple coincidences of chains in complete $q$-ary trees and forests with randomly marked vertices
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2022
SP  - 8
EP  - 11
IS  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2022_15_a1/
LA  - ru
ID  - PDMA_2022_15_a1
ER  - 
%0 Journal Article
%A V. G. Mikhailov
%A V. I. Kruglov
%T Asymptotic normality of number of multiple coincidences of chains in complete $q$-ary trees and forests with randomly marked vertices
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2022
%P 8-11
%N 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2022_15_a1/
%G ru
%F PDMA_2022_15_a1
V. G. Mikhailov; V. I. Kruglov. Asymptotic normality of number of multiple coincidences of chains in complete $q$-ary trees and forests with randomly marked vertices. Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 8-11. http://geodesic.mathdoc.fr/item/PDMA_2022_15_a1/

[1] Guibas L. J. and Odlyzko A. M., “Long repetitive patterns in random sequences”, Z. Wahrscheinlichkeitstheorie verw. Geb., 1980, no. 1, 241–262 | DOI | MR | Zbl

[2] 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 | Zbl

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

[4] Kruglov V. and Zubkov A., “Number of pairs of template matchings in $q$-ary tree with randomly marked vertices”, LNCS, 10684, 2017, 336–346 | Zbl

[5] Hoffmann C. M. and O'Donnell M. J., “Pattern matching in trees”, J. ACM, 29:1 (1982), 68–95 | DOI | MR | Zbl

[6] Steyaert J.-M. and Flajolet P., “Patterns and pattern-matching in trees: an analysis”, Inf. Control, 58:1 (1983), 19–58 | DOI | MR | Zbl

[7] Singh G., Smolka S. A., and Ramakrishnan I. V., “Distributed algorithms for tree pattern matching”, LNCS, 312, 1988, 92–107 | MR | Zbl

[8] Tahraoui M. A., Pinel-Sauvagnat K., Laitang C., et al., “A survey on tree matching and XML retrieval”, Computer Science Rev., 2013, no. 8, 1–23 | DOI | Zbl

[9] Zubkov A. M., Kruglov V. I., “Povtoreniya tsepochek na binarnom dereve so sluchainymi metkami vershin”, Diskretnaya matematika, 27:4 (2015), 38–48

[10] Kruglov V. I., “On coincidences of tuples in a $q$-ary tree with random labels of vertices”, Discr. Math. Appl., 28:5 (2018), 293–307 | DOI | MR | Zbl

[11] Mikhailov V. G., Kruglov V. I., “Ob asimptoticheskoi normalnosti v zadache o povtoreniyakh tsepochek v pomechennom polnom dereve”, Matem. vopr. kriptogr., 12:4 (2021), 59–64 | MR | Zbl

[12] Janson S., “Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs”, Ann. Probab., 16:1 (1988), 306–312 | DOI | MR

[13] Mikhailov V. G., “Ob odnoi teoreme Yansona”, Teoriya veroyatn. i ee primen., 36:1 (1991), 168–170 | MR