Geodesic
Almost sure asymptotic expansions for profiles of simply generated random trees
Teoriâ slučajnyh processov, Tome 24 (2019) no. 1, pp. 49-63.

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

This paper is a continuation of the analysis of Edgeworth expansions for one-split branching random walk and its application to random trees. We provide new results for profile, mode and width for several simply generated random trees, in particular for random recursive trees, $p$-oriented recursive trees and $D$-ary random trees. Our results are corollaries of a general Edgeworth expansion for a one-split branching random walk proved by Kabluchko, Marynych and Sulzbach [The Annals of Applied Probability 27(6): 3478–3524, 2017]. We derive an additional characterization of the random variables appearing in the coefficients of the asymptotic expansions by calculating explicitly corresponding fixed-point equations of a branching type. We further provide numerical simulations justifying our theoretical findings.
Keywords: binary search tree, branching random walk, $D$-ary tree, Edgeworth expansion, fixed-point equation, one-split branching random walk, $p$-oriented recursive tree, profile, random analytic function, random recursive tree, random tree, width.
Mots-clés : mode, PORT, simulation 
@article{THSP_2019_24_1_a3,
     author = {Vladyslav Bogun},
     title = {Almost sure asymptotic expansions for profiles of simply generated random trees},
     journal = {Teori\^a slu\v{c}ajnyh processov},
     pages = {49--63},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/THSP_2019_24_1_a3/}
}
TY  - JOUR
AU  - Vladyslav Bogun
TI  - Almost sure asymptotic expansions for profiles of simply generated random trees
JO  - Teoriâ slučajnyh processov
PY  - 2019
SP  - 49
EP  - 63
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/THSP_2019_24_1_a3/
LA  - en
ID  - THSP_2019_24_1_a3
ER  - 
%0 Journal Article
%A Vladyslav Bogun
%T Almost sure asymptotic expansions for profiles of simply generated random trees
%J Teoriâ slučajnyh processov
%D 2019
%P 49-63
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/THSP_2019_24_1_a3/
%G en
%F THSP_2019_24_1_a3
Vladyslav Bogun. Almost sure asymptotic expansions for profiles of simply generated random trees. Teoriâ slučajnyh processov, Tome 24 (2019) no. 1, pp. 49-63. http://geodesic.mathdoc.fr/item/THSP_2019_24_1_a3/

[1] B. Chauvin, M. Drmota, J. Jabbour-Hattab, “The profile of binary search trees”, Ann. Appl. Probab., 11:4 (2001), 1042–1062 | DOI | MR | Zbl

[2] B. Chauvin, T. Klein, J.-F. Marckert, A. Rouault, “Martingales and profile of binary search trees”, Elect. J. Probab., 10 (2005), 420–435 | DOI | MR | Zbl

[3] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel Publishing Company, 1974 | MR | Zbl

[4] L. Devroye, Non-Uniform Random Variate Generation, Springer-Verlag, 1986 | MR | Zbl

[5] L. Devroye, H.-K. Hwang, “Width and mode of the profile for some random trees of logarithmic height”, Ann. Appl. Probab., 16:2 (2006), 886–918 | DOI | MR | Zbl

[6] M. Drmota, Random trees: An interplay between combinatorics and probability, Springer–Verlag, Wien, 2009 | MR | Zbl

[7] M. Drmota, H.-K. Hwang, “Profiles of random trees: Correlation and width of random recursive trees and binary search trees”, Advances in Applied Probability, 37:2 (2005), 321–341 | DOI | MR | Zbl

[8] M. Drmota, S. Janson, R. Neininger, “A functional limit theorem for the profile of search trees”, Ann. Appl. Probab., 18:1 (2008), 288–333 | DOI | MR | Zbl

[9] V. Feray, P.-L. Meliot, A. Nikeghbali, Mod-$\phi$ Convergence: Normality Zones and Precise Deviations, SpringerBriefs in Probability and Mathematical Statistics. Springer International Publishing, 2016 | MR | Zbl

[10] R. Gouet, “Strong Convergence of Proportions in a Multicolor Polya Urn”, Journal of Applied Probability, 34:2 (1997), 426–435 | DOI | MR | Zbl

[11] M. Fuchs, H.-K. 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

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

[13] J. Jacod, E. Kowalski, A. Nikeghbali, “Mod-Gaussian convergence: new limit theorems in probability and number theory”, Forum Math., 23:4 (2011), 835–873 | DOI | MR | Zbl

[14] Z. Kabluchko, A. Marynych, H. Sulzbach, General Edgeworth expansions with applications to profiles of random trees, 27:6 (2017), 3478–3524 | MR | Zbl

[15] Z. Katona, “Width of a scale-free tree”, J. Appl. Probab., 42:3 (2005), 839–850 | DOI | MR | Zbl

[16] E. Kowalski, A. Nikeghbali, “Mod-Poisson convergence in probability and number theory”, Int. Math. Res. Not. IMRN, 2010, no. 18, 3549–3587 | DOI | MR | Zbl

[17] H. Mahmound, Polya urn models, CRC Press, 2009 | MR

[18] U. Roster, “A limit theorem for “Quicksort””, RAIRO Inform. Theor. Appl., 25:1 (1991), 85–100 | DOI | MR

[19] E.-M. Schopp, “A functional limit theorem for the profile of b-ary trees”, Ann. Appl. Probab., 20:3 (2010), 907–950 | DOI | MR | Zbl

[20] H. Sulzbach, “A functional limit law for the profile of plane-oriented recursive trees”, In Fifth Colloquium on Mathematics and Computer Science, Discrete Math. Theor. Comput. Sci. Proc., AI, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2008, 339–350 | MR | Zbl