Geodesic
Conditions for asymptotic normality of the number of multiple repetitions of chains in marked complete trees and forests
Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 1, pp. 85-97 
V. G. Mikhailov; V. I. Kruglov. Conditions for asymptotic normality of the number of multiple repetitions of chains in marked complete trees and forests. Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 1, pp. 85-97. http://geodesic.mathdoc.fr/item/MVK_2023_14_1_a5/
@article{MVK_2023_14_1_a5,
     author = {V. G. Mikhailov and V. I. Kruglov},
     title = {Conditions for asymptotic normality of the number of multiple repetitions of chains in marked complete trees and forests},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {85--97},
     year = {2023},
     volume = {14},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2023_14_1_a5/}
}
TY  - JOUR
AU  - V. G. Mikhailov
AU  - V. I. Kruglov
TI  - Conditions for asymptotic normality of the number of multiple repetitions of chains in marked complete trees and forests
JO  - Matematičeskie voprosy kriptografii
PY  - 2023
SP  - 85
EP  - 97
VL  - 14
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MVK_2023_14_1_a5/
LA  - ru
ID  - MVK_2023_14_1_a5
ER  - 
%0 Journal Article
%A V. G. Mikhailov
%A V. I. Kruglov
%T Conditions for asymptotic normality of the number of multiple repetitions of chains in marked complete trees and forests
%J Matematičeskie voprosy kriptografii
%D 2023
%P 85-97
%V 14
%N 1
%U http://geodesic.mathdoc.fr/item/MVK_2023_14_1_a5/
%G ru
%F MVK_2023_14_1_a5

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 the set $\{1,2,\ldots, N\}$ and forests of such trees. For both cases we investigate the number of sets of $r\ge 2$ paths with fixed length $s$ such that corresponding $s$-chains of marks of vertices are identical. We propose three theorems on sufficient conditions for the asymptotic normality for considered random values as $H\to\infty$ and possibly varying parameters $s$ and $q$.

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

[2] Mikhailov V.G., Kruglov V.I., “Ob asimptoticheskoi normalnosti v zadache o povtoreniyakh tsepochek v pomechennom polnom dereve”, Matematicheskie voprosy kriptografii, 12:4 (2021), 59–64 | DOI | MR | Zbl

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

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

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

[6] Zubkov A. M., Kruglov V. I., “Povtoreniya tsepochek na binarnom dereve so sluchainymi metkami vershin”, Diskret. matem., 27:4 (2015), 38–48 | DOI

[7] Kruglov V., Zubkov A., “Number of Pairs of Template Matchings in $q$-ary Tree with Randomly Marked Vertices”, Analytical and Computational Methods in Probability Theory, Lecture Notes in Comput. Sci., 10684, 2017, 336–346 | DOI | Zbl

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

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

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

[11] Singh G., Smolka S.A., Ramakrishnan I.V., “Distributed algorithms for tree pattern matching”, Lect. Notes Comput. Sci., 312, 1988, 92–107 | DOI | MR | Zbl

[12] Tahraoui M.A., Pinel-Sauvagnat K., Laitang C., Boughanem M., Kheddouci H., Ning L., “A survey on tree matching and XML retrieval”, Comput. Sci. Rev., 8 (2013), 1–23 | DOI | Zbl

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

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