Geodesic
Normal limit law for protected node profile of random recursive trees
Teoriâ veroâtnostej i ee primeneniâ, Tome 67 (2022) no. 3, pp. 563-578 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Protected nodes, i.e., nodes with distance at least 2 to each leaf, have been studied in various classes of random rooted trees. In this short note, we investigate the protected node profile, i.e., the number of protected nodes with the same distance from the root in random recursive trees. Here, when the limit ratio of the level and logarithm of tree size is zero, we present the asymptotic expectations, variances, and covariance of the protected node profile and the nonprotected node profile in random recursive trees. We also show that protected node and nonprotected node profiles have a bivariate normal limiting distribution via the joint characteristic function and singularity analysis.
Keywords: random recursive trees, profile, protected node, characteristic function, singularity analysis, Berry–Esseen inequality.
Mots-clés : bivariate normal distribution 
@article{TVP_2022_67_3_a7,
     author = {J. Toofanpour and M. Javanian and R. Imany-Nabiyyi},
     title = {Normal limit law for protected node profile of random recursive trees},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {563--578},
     year = {2022},
     volume = {67},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2022_67_3_a7/}
}
TY  - JOUR
AU  - J. Toofanpour
AU  - M. Javanian
AU  - R. Imany-Nabiyyi
TI  - Normal limit law for protected node profile of random recursive trees
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2022
SP  - 563
EP  - 578
VL  - 67
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TVP_2022_67_3_a7/
LA  - ru
ID  - TVP_2022_67_3_a7
ER  - 
%0 Journal Article
%A J. Toofanpour
%A M. Javanian
%A R. Imany-Nabiyyi
%T Normal limit law for protected node profile of random recursive trees
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2022
%P 563-578
%V 67
%N 3
%U http://geodesic.mathdoc.fr/item/TVP_2022_67_3_a7/
%G ru
%F TVP_2022_67_3_a7
J. Toofanpour; M. Javanian; R. Imany-Nabiyyi. Normal limit law for protected node profile of random recursive trees. Teoriâ veroâtnostej i ee primeneniâ, Tome 67 (2022) no. 3, pp. 563-578. http://geodesic.mathdoc.fr/item/TVP_2022_67_3_a7/

[1] L. Devroye, S. Janson, “Protected nodes and fringe subtrees in some random trees”, Electron. Commun. Probab., 19 (2014), 6, 10 pp. | DOI | MR | Zbl

[2] M. Dondajewski, J. Szymański, “On the distribution of vertex-degrees in a strata of a random recursive tree”, Bull. Acad. Polon. Sci. Sér. Sci. Math., 30:5-6 (1982), 205–209 | MR | Zbl

[3] M. Drmota, Random trees. An interplay between combinatorics and probability, Springer-Verlag, Vienna, 2009, xviii+458 pp. | DOI | MR | Zbl

[4] M. Drmota, M. Fuchs, Hsien-Kuei Hwang, R. Neininger, “Node profiles of symmetric digital search trees: concentration properties”, Random Structures Algorithms, 58:3 (2021), 430–467 ; (2020 (v1 – 2017)), 34 pp., arXiv: 1711.06941 | DOI | MR

[5] P. Flajolet, A. Odlyzko, “Singularity analysis of generating functions”, SIAM J. Discrete Math., 3:2 (1990), 216–240 | DOI | MR | Zbl

[6] M. Fuchs, Hsien-Kuei Hwang, R. Neininger, “Profiles of random trees: limit theorems for random recursive trees and binary search trees”, Algorithmica, 46:3-4 (2006), 367–407 | DOI | MR | Zbl

[7] M. Fuchs, C. K. Lee, G. R. Yu, “On 2-protected nodes in random digital trees”, Theoret. Comput. Sci., 622 (2016), 111–122 | DOI | MR | Zbl

[8] C. Heuberger, S. Kropf, “Higher dimensional quasi-power theorem and Berry–Esseen inequality”, Monatsh. Math., 187:2 (2018), 293–314 | DOI | MR | Zbl

[9] Hsien-Kuei Hwang, “Asymptotic expansions for the stirling numbers of the first kind”, J. Combin. Theory Ser. A, 71:2 (1995), 343–351 | DOI | MR | Zbl

[10] Hsien-Kuei Hwang, “Profiles of random trees: plane-oriented recursive trees”, Random Structures Algorithms, 30:3 (2007), 380–413 | DOI | MR | Zbl

[11] Hsien-Kuei Hwang, M. Fuchs, V. Zacharovas, “Asymptotic variance of random symmetric digital search trees”, Discrete Math. Theor. Comput. Sci., 12:2 (2010), 103–165 | MR | Zbl

[12] M. Javanian, “Protected node profile of tries”, Discrete Math. Theor. Comput. Sci., 20:1 (2018), 12, 20 pp. | MR | Zbl

[13] H. M. Mahmoud, M. D. Ward, “Asymptotic properties of protected nodes in random recursive trees”, J. Appl. Probab., 52:1 (2015), 290–297 | DOI | MR | Zbl

[14] A. Meir, J. W. Moon, “Cutting down recursive trees”, Math. Biosci., 21:3-4 (1974), 173–181 | DOI | Zbl

[15] A. Meir, J. W. Moon, “On the altitude of nodes in random trees”, Canad. J. Math., 30:5 (1978), 997–1015 | DOI | MR | Zbl

[16] G. Park, Hsien-Kuei Hwang, P. Nicodème, W. Szpankowski, “Profiles of tries”, SIAM J. Comput., 38:5 (2009), 1821–1880 | DOI | MR | Zbl

[17] V. V. Petrov, Sums of independent random variables, Ergeb. Math. Grenzgeb., 82, Springer-Verlag, New York–Heidelberg, 1975, x+346 pp. | DOI | MR | MR | Zbl | Zbl

[18] S. M. Sadikova, “Two-dimensional analogues of an inequality of Esseen with applications to the central limit theorem”, Theory Probab. Appl., 11:3 (1966), 325–335 | DOI | MR | Zbl

[19] R. T. Smythe, H. M. Mahmoud, “A survey of recursive trees”, Theory Probab. Math. Stat., 51 (1995), 1–27 | MR | Zbl

[20] P. Van Mieghem, G. Hooghiemstra, R. van der Hofstad, “On the efficiency of multicast”, IEEE/ACM Trans. Netw., 9:6 (2001), 719–732 | DOI