×

A functional limit theorem for the profile of random recursive trees. (English) Zbl 1406.60051

Summary: Let \(X_n(k)\) be the number of vertices at level \(k\) in a random recursive tree with \(n+1\) vertices. We prove a functional limit theorem for the vector-valued process \((X_{[n^t]}(1),\dots , X_{[n^t]}(k))_{t\geq 0}\), for each \(k\in \mathbb N\). We show that after proper centering and normalization, this process converges weakly to a vector-valued Gaussian process whose components are integrated Brownian motions. This result is deduced from a functional limit theorem for Crump-Mode-Jagers branching processes generated by increasing random walks with increments that have finite second moment. Let \(Y_k(t)\) be the number of the \(k\)th generation individuals born at times \(\leq t\) in this process. Then, it is shown that the appropriately centered and normalized vector-valued process \((Y_{1}(st),\dots , Y_k(st))_{t\geq 0}\) converges weakly, as \(s\rightarrow \infty \), to the same limiting Gaussian process as above.

MSC:

60F17 Functional limit theorems; invariance principles
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60G50 Sums of independent random variables; random walks
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Backhausz, A. and Móri, T. F.: Degree distribution in the lower levels of the uniform recursive tree. Annales Univ. Sci. Budapest., Sect. Comp.36, (2012), 53–62. · Zbl 1249.05355
[2] Billingsley, P.: Convergence of probability measures. John Wiley & Sons, Inc., New York-London-Sydney, 1968. xii+253 pp. · Zbl 0172.21201
[3] Carlsson, H. and Nerman, O.: An alternative proof of Lorden’s renewal inequality. Adv. Appl. Probab.18, (1986), 1015–1016. · Zbl 0606.60082
[4] Chauvin, B., Drmota, M. and Jabbour-Hattab, J.: The profile of binary search trees. Ann. Appl. Probab.11, (2001), 1042–1062. · Zbl 1012.60038
[5] Chauvin, B., Klein, T., Marckert, J.-F. and Rouault, A.: Martingales and profile of binary search trees. Electron. J. Probab.10, (2005), 420–435. · Zbl 1109.60059
[6] Devroye, L.: Branching processes in the analysis of the heights of trees. Acta Inform.24, (1987), 277–298. · Zbl 0643.60065
[7] Drmota, M.: Random trees. An interplay between combinatorics and probability. SpringerWienNewYork, Vienna, 2009. xviii+458 pp. · Zbl 1170.05022
[8] Drmota, M., Janson, S. and Neininger, R.: A functional limit theorem for the profile of search trees. Ann. Appl. Probab.18, (2008), 288–333. · Zbl 1143.68019
[9] Flajolet, Ph. and Sedgewick, R.: Analytic combinatorics. Cambridge University Press, Cambridge, 2009. xiv+810 pp. · Zbl 1165.05001
[10] Fuchs, M., Hwang, H.-K. and Neininger, R.: Profiles of random trees: limit theorems for random recursive trees and binary search trees. Algorithmica. 46, (2006), 367–407. · Zbl 1106.68083
[11] Gut, A.: On the moments and limit distributions of some first passage times. Ann. Probab.2, (1974), 277–308. · Zbl 0278.60031
[12] Gut, A: Stopped random walks. Limit theorems and applications. 2nd Edition, Springer, New York, 2009. xiv+263 pp. · Zbl 1166.60001
[13] Iksanov, A.: Functional limit theorems for renewal shot noise processes with increasing response functions. Stoch. Proc. Appl.123, (2013), 1987–2010. · Zbl 1302.60058
[14] Iksanov, A.: Renewal theory for perturbed random walks and similar processes. Birkhäuser/Springer, Cham, 2016. xiv+250 pp. · Zbl 1382.60004
[15] Iksanov, A., Marynych, A. and Meiners, M.: Moment convergence of first-passage times in renewal theory. Stat. Probab. Letters. 119, (2016), 134–143. · Zbl 1350.60091
[16] Iksanov, A., Marynych, A. and Meiners, M.: Asymptotics of random processes with immigration I: Scaling limits. Bernoulli. 23, (2017), 1233–1278. · Zbl 1386.60122
[17] Jabbour-Hattab, J.: Martingales and large deviations for binary search trees. Random Struct. Algor.19, (2001), 112–127. · Zbl 0983.60034
[18] Kabluchko, Z., Marynych, A. and Sulzbach, H.: General Edgeworth expansions with applications to profiles of random trees. Ann. Appl. Probab.27, (2017), 3478–3524. · Zbl 1382.60068
[19] Pittel, B.: Note on the heights of random recursive trees and random \(m\)-ary search trees. Random Struct. Algor.5, (1994), 337–347. · Zbl 0790.05077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.