Asymptotic normality of number of multiple coincidences of chains in complete q-ary trees and forests with randomly marked vertices
We consider complete q-ary trees of height H with vertices marked by random independent marks taking values from some the set f1; 2; : : : ;Ng. The object of our research is the number of tuples of r > 2 paths having the same length s and identical sequences of vertex marks. We propose a theorem on su cient conditions of asymptotic normality of considered random values for the case when height of the tree tends to in nity. We also investigate repetitions of chains in forest of trees and suppose that there are r trees which may have di erent heights H1; : : : ;Hr 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 su cient conditions of asymptotic normality.
Keywords
marked trees,
chains of marks,
chains on a tree,
repetitions of chains,
conditions of asymptotic normalityAuthors
| Mikhailov Vladimir A. | Mathematical Institute. V. A. Steklov RAS | mikhail@mi-ras.ru |
| Kruglov Vasiliy I. | Mathematical Institute. V. A. Steklov RAS | kruglov@mi-ras.ru |
Всего: 2
References
Guibas L. J. and Odlyzko A. M. Long repetitive patterns in random sequences // Z. Wahrscheinlichkeitstheorie verw. Geb. 1980. No. 1. P. 241-262.
Зубков А. М., Михайлов В. Г. Предельные распределения случайных величин, связанных с длинными повторениями в последовательности независимых испытаний // Теория ве-роятн. и ее примен. 1974. Т. 19. № 1. С. 173-181.
Михайлов В. Г. Оценка точности сложной пуассоновской аппроксимации для распределения числа совпадающих цепочек // Теория вероятн. и ее примен. 2001. Т. 46. № 4. С. 713-723.
Kruglov V. and Zubkov A. Number of pairs of template matchings in q-ary tree with randomly marked vertices // LNCS. 2017. V. 10684. P. 336-346.
Hoffmann C. M. and O'Donnell M. J. Pattern matching in trees //j. ACM. 1982. V. 29. No. 1. P. 68-95.
Steyaert J.-M. and Flajolet P. Patterns and pattern-matching in trees: an analysis // Inf. & Control. 1983. V. 58. No. 1. P. 19-58.
Singh G., Smolka S. A., and Ramakrishnan I. V. Distributed algorithms for tree pattern matching // LNCS. 1988. V. 312. P. 92-107.
Tahraoui M. A., Pinel-Sauvagnat K., Laitang C., et al. A survey on tree matching and XML retrieval // Computer Science Rev. 2013. No. 8. P. 1-23.
Зубков А.М., Круглов В.И. Повторения цепочек на бинарном дереве со случайными метками вершин // Дискретная математика. 2015. Т. 27. № 4. С. 38-48.
Kruglov V. I. On coincidences of tuples in a q-ary tree with random labels of vertices // Discr. Math. Appl. 2018. V. 28. No. 5. P. 293-307.
Михайлов В. Г., Круглов В. И. Об асимптотической нормальности в задаче о повторениях цепочек в помеченном полном дереве // Матем. вопр. криптогр. 2021. Т. 12. №4. С. 59-64.
Janson S. Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs // Ann. Probab. 1988. V. 16. No. 1. P. 306-312.
Михайлов В. Г. Об одной теореме Янсона // Теория вероятн. и ее примен. 1991. Т. 36. №1. С. 168-170.
