General Edgeworth expansions with applications to profiles of random trees. (English) Zbl 1382.60068

Kabluchko, Zakhar; Marynych, Alexander; Sulzbach, Henning

Ann. Appl. Probab. 27, No. 6, 3478-3524 (2017).

Summary: 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 [L. Devroye and H.-K. Hwang, ibid. 16, No. 2, 886–918 (2006; Zbl 1128.60008); M. Fuchs et al., Algorithmica 46, No. 3–4, 367–407 (2006; Zbl 1106.68083); M. Drmota and H.-K. Hwang, Adv. Appl. Probab. 37, No. 2, 321–341 (2005; Zbl 1073.60006)]. The aforementioned results are special cases and corollaries of a general theorem: an Edgeworth expansion for an arbitrary sequence of random or deterministic functions \(\mathbb{L}_{n}:\mathbb{Z}\rightarrow\mathbb{R}\) which converges in the mod-\(\phi\)-sense. Applications to Stirling numbers of the first kind will be given in a separate paper.

MSC:

60G50	Sums of independent random variables; random walks
60F05	Central limit and other weak theorems
60J80	Branching processes (Galton-Watson, birth-and-death, etc.)
60J85	Applications of branching processes
60F10	Large deviations
60F15	Strong limit theorems

Keywords:

biggins martingale; branching random walk; central limit theorem; Edgeworth expansion; mod-phi convergence; mode; profile; random analytic function; random tree; width

Citations:

Zbl 1128.60008; Zbl 1106.68083; Zbl 1073.60006

References:

[1]	Athreya, K. B. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems.Ann. Math. Stat.391801-1817. · Zbl 0185.46103
[2]	Bergeron, F., Flajolet, P. and Salvy, B. (1992). Varieties of increasing trees. InCAAP ’92 (Rennes, 1992).Lecture Notes in Computer Science58124-48. Springer, Berlin.
[3]	Biggins, J. D. (1992). Uniform convergence of martingales in the branching random walk.Ann. Probab.20137-151. · Zbl 0748.60080
[4]	Biggins, J. D. and Grey, D. R. (1979). Continuity of limit random variables in the branching random walk.J. Appl. Probab.16740-749. · Zbl 0425.60069
[5]	Biggins, J. D. and Grey, D. R. (1997). A note on the growth of random trees.Statist. Probab. Lett.32339-342. · Zbl 0904.60067
[6]	Chauvin, B., Drmota, M. and Jabbour-Hattab, J. (2001). The profile of binary search trees.Ann. Appl. Probab.111042-1062. · Zbl 1012.60038
[7]	Chauvin, B., Klein, T., Marckert, J.-F. and Rouault, A. (2003). Martingales, embedding and tilting of binary trees. Preprint. · Zbl 1109.60059
[8]	Chauvin, B., Klein, T., Marckert, J.-F. and Rouault, A. (2005). Martingales and profile of binary search trees.Electron. J. Probab.10420-435. · Zbl 1109.60059
[9]	Chauvin, B. and Rouault, A. (2004). Connecting Yule process, bisection and binary search tree via martingales.J. Iran. Stat. Soc.(JIRSS)389-116. · Zbl 1499.60262
[10]	Chen, X. (2001). Exact convergence rates for the distribution of particles in branching random walks.Ann. Appl. Probab.111242-1262. · Zbl 1012.60080
[11]	Delbaen, F., Kowalski, E. and Nikeghbali, A. (2015). Mod-\(φ\) convergence.Int. Math. Res. Not. IMRN11 3445-3485. · Zbl 1319.60040
[12]	Devroye, L. (1986). A note on the height of binary search trees.J. ACM33489-498. · Zbl 0741.05062
[13]	Devroye, L. (1987). Branching processes in the analysis of the heights of trees.Acta Inform.24277-298. · Zbl 0643.60065
[14]	Devroye, L. and Hwang, H.-K. (2006). Width and mode of the profile for some random trees of logarithmic height.Ann. Appl. Probab.16886-918. · Zbl 1128.60008
[15]	Drmota, M. (2009).Random Trees:An Interplay Between Combinatorics and Probability. Springer, Vienna. · Zbl 1170.05022
[16]	Drmota, M. and Hwang, H.-K. (2005). Profiles of random trees: Correlation and width of random recursive trees and binary search trees.Adv. in Appl. Probab.37321-341. · Zbl 1073.60006
[17]	Drmota, M., Janson, S. and Neininger, R. (2008). A functional limit theorem for the profile of search trees.Ann. Appl. Probab.18288-333. · Zbl 1143.68019
[18]	Erdös, P. (1953). On a conjecture of Hammersley.J. Lond. Math. Soc.28232-236. · Zbl 0050.27003
[19]	Féray, V., Méliot, P.-L. and Nikeghbali, A. (2016).Mod-\(ϕ\) Convergence:Normality Zones and Precise Deviations. Springer, Berlin. · Zbl 1387.60003
[20]	Fuchs, M., Hwang, H.-K. and Neininger, R. (2006). Profiles of random trees: Limit theorems for random recursive trees and binary search trees.Algorithmica46367-407. · Zbl 1106.68083
[21]	Grübel, R. and Kabluchko, Z. (2016). A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees.Ann. Appl. Probab.263659-3698. · Zbl 1367.60028
[22]	Grübel, R. and Kabluchko, Z. (2017). Edgeworth expansions for profiles of lattice branching random walks.Ann. Inst. Henri Poincaré Probab. Stat.532103-2134. · Zbl 1387.60075
[23]	Hwang, H.-K. (2007). Profiles of random trees: Plane-oriented recursive trees.Random Structures Algorithms30380-413. · Zbl 1115.05083
[24]	Jabbour-Hattab, J. (2001). Martingales and large deviations for binary search trees.Random Structures Algorithms19112-127. · Zbl 0983.60034
[25]	Jacod, J., Kowalski, E. and Nikeghbali, A. (2011). Mod-Gaussian convergence: New limit theorems in probability and number theory.Forum Math.23835-873. · Zbl 1225.15035
[26]	Kabluchko, Z. (2012). Distribution of levels in high-dimensional random landscapes.Ann. Appl. Probab.22337-362. · Zbl 1246.60036
[27]	Kabluchko, Z., Marynych, A. and Sulzbach, H. (2016). General Edgeworth expansions with applications to profiles of random trees: Extended version. Available athttp://www.math.uni-muenster.de/statistik/kabluchko/files/edgeworth_full.pdf. · Zbl 1367.11029
[28]	Kabluchko, Z., Marynych, A. and Sulzbach, H. (2016). Mode and Edgeworth expansion for the Ewens distribution and the Stirling numbers.J. Integer Seq.19Art. 16.8.8. · Zbl 1367.11029
[29]	Katona, Z. (2005). Width of a scale-free tree.J. Appl. Probab.42839-850. · Zbl 1079.05090
[30]	Kowalski, E. and Nikeghbali, A. (2010). Mod-Poisson convergence in probability and number theory.Int. Math. Res. Not. IMRN18 3549-3587. · Zbl 1292.11104
[31]	Kowalski, E. and Nikeghbali, A. (2012). Mod-Gaussian convergence and the value distribution of \(ζ(\frac{1}{2}+it)\) and related quantities.J. Lond. Math. Soc.(2)86291-319. · Zbl 1292.11103
[32]	Kuba, M. and Panholzer, A. (2007). The left-right-imbalance of binary search trees.Theoret. Comput. Sci.370265-278. · Zbl 1118.68052
[33]	Mahmoud, H. M. (1992).Evolution of Random Search Trees. Wiley, New York. · Zbl 0762.68033
[34]	Méliot, P.-L. and Nikeghbali, A. (2015). Mod-Gaussian convergence and its applications for models of statistical mechanics. InIn Memoriam Marc Yor—Séminaire de Probabilités XLVII. Lecture Notes in Math.2137369-425. Springer, Cham. · Zbl 1336.60046
[35]	Pittel, B. (1984). On growing random binary trees.J. Math. Anal. Appl.103461-480. · Zbl 0593.60014
[36]	Régnier, M. (1989). A limiting distribution for quicksort.RAIRO Theor. Inform. Appl.23335-343. · Zbl 0677.68072
[37]	Rösler, U. (1991). A limit theorem for “Quicksort”.RAIRO Theor. Inform. Appl.2585-100. · Zbl 0718.68026
[38]	Schopp, E.-M. (2010). A functional limit theorem for the profile of \(b\)-ary trees.Ann. Appl. Probab.20907-950.
[39]	Sulzbach, H. (2008). A functional limit law for the profile of plane-oriented recursive trees. InFifth Colloquium on Mathematics and Computer Science. 339-350. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1355.05229
[40]	Sulzbach, H. (2017). On martingale tail sums for the path length in random trees.Random Structures Algorithms50493-508. · Zbl 1364.05067
[41]	Uchiyama, K. (1982). Spatial growth of a branching process of particles living in \(\textbf{R}^d \).Ann. Probab.10896-918. · Zbl 0499.60088