On coincidences of tuples in a $q$-ary tree with random labels of vertices

V. I. Kruglov

Diskretnaya Matematika, Tome 30 (2018) no. 3, pp. 48-67.

Résumé

Let all vertices of a complete $q$-ary tree of finite height be independently and equiprobably labeled by the elements of some finite alphabet. We consider the numbers of pairs of identical tuples of labels on chains of subsequent vertices in the tree. Exact formulae for the expectations of these numbers are obtained, convergence to the compound Poisson distribution is proved. For the size of cluster composed by pairs of identically labeled chains we also obtain exact formula for the expectation.

Détail

Keywords: $q$-ary trees with random labels, matches of labels, sums of dependent indicators, Poisson approximation.

Bibliographie

[1] Erhardsson T., “Stein's method for Poisson and compound Poisson approximation”: Barbour A. D., Chen L. H. Y. (ed.), An introduction to Stein's method, Singapore Univ. Press, 2005, 61–113 | DOI | MR

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

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

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

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

[6] Rowland E. S., “Pattern avoidance in binary trees”, arXiv: 0809.0488 | MR

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

[8] 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 | MR | Zbl

[9] Mikhailov V. G., “Otsenka tochnosti slozhnoi puassonovskoi approksimatsii dlya raspredeleniya chisla sovpadayuschikh tsepochek”, Teoriya veroyatn. i ee primen., 46:4 (2001), 713–723 ; Mikhailov V. G., “Estimate of the accuracy of the compound poisson approximation for the distribution of the number of matching patterns”, Theory Probab. Appl., 46:4 (2002), 667–675 | DOI | MR | Zbl | DOI

[10] Mikhailov V. G., “Otsenki tochnosti puassonovskoi approksimatsii dlya raspredeleniya chisla serii povtorenii dlinnykh tsepochek v tsepi Markova”, Diskretnaya matematika, 27:4 (2015), 67–78 ; Mikhaylov 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 | MR | Zbl | DOI | Zbl

[11] Mikhailov V. G., “O veroyatnosti nalichiya v sluchainoi posledovatelnosti tsepochek s odinakovoi strukturoi”, Diskretnaya matematika, 28:3 (2016), 97–110 ; Mikhailov V. G., “On the probability of existence of substrings with the same structure in a random sequence”, Discrete Math. Appl., 27:6 (2017), 377–386 | DOI | MR | DOI | Zbl

[12] Zubkov A. M., Kruglov V. I., “Povtoreniya tsepochek na binarnom dereve so sluchainymi metkami vershin”, Diskretnaya matematika, 27:4 (2015), 38–48 ; Zubkov A. M., Kruglov V. I., “On coincidences of tuples in a binary tree with random labels of vertices”, Discrete Math. Appl., 26:3 (2016), 145–153 | DOI | MR | Zbl | DOI

[13] 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, Lect. Notes Comput. Sci., 10684, 2017, 336–346 | DOI | Zbl