|
Almost sure asymptotic expansions for profiles of simply generated random trees
Vladyslav Bogun Faculty of Computer Science and Cybernetics, Taras Shevchenko National University of Kyiv, 01601 Kyiv, Ukraine
Abstract:
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, mode, one-split branching random walk, $p$-oriented recursive tree, PORT, profile, random analytic function, random recursive tree, random tree, simulation, width.
Citation:
Vladyslav Bogun, “Almost sure asymptotic expansions for profiles of simply generated random trees”, Theory Stoch. Process., 24(40):1 (2019), 49–63
Linking options:
https://www.mathnet.ru/eng/thsp300 https://www.mathnet.ru/eng/thsp/v24/i1/p49
|
Statistics & downloads: |
Abstract page: | 69 | Full-text PDF : | 17 | References: | 12 |
|