GENERAL EDGEWORTH EXPANSIONS WITH APPLICATIONS TO PROFILES OF RANDOM TREES

• 成果类型: Article
• 署名作者: Kabluchko, Zakhar; Marynych, Alexander; Sulzbach, Henning
• 署名单位: University of Munster; Ministry of Education & Science of Ukraine; Taras Shevchenko National University of Kyiv; McGill University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/17-AAP1285
• 发表日期: 2017
• 页码: 3478-3524
• 关键词: mod-gaussian convergence; functional limit-theorem; random recursive trees; branching-processes; martingales; width; particles; GROWTH

摘要

We prove an asymptotic Edgeworth expansion for the profiles of certain random trees including binary search trees, random recursive trees and plane-oriented random trees, as the size of the tree goes to infinity. All these models can be seen as special cases of the one-split branching random walk for which we also provide an Edgeworth expansion. These expansions lead to new results on mode, width and occupation numbers of the trees, settling several open problems raised in Devroye and Hwang [Ann. Appl. Probab. 16 (2006) 886-918], Fuchs, Hwang and Neininger [Algorithmica 46 (2006) 367-407], and Drmota and Hwang [Adv. in Appl. Probab. 37 (2005) 321-341]. The aforementioned results are special cases and corollaries of a general theorem: an Edgeworth expansion for an arbitrary sequence of random or deterministic functions L-n : Z -> R which converges in the mod-phi-sense. Applications to Stirling numbers of the first kind will be given in a separate paper.