Weak convergence of the number of vertices at intermediate levels of random recursive trees

DOI10.1017/JPR.2018.75MaRDI QIDQ4611274zbMATH OpenOpenAlexWikidataFDO

Authors Zakhar Kabluchko, Alexander Iksanov

Publication date 17 January 2019

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.10872

zbMATH Keywords

Gaussian processweak convergencerandom recursive treeCrump-Mode-Jagers branching processintermediate level

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: Let $X_n(k)$ be the number of vertices at level $k$ in a random recursive tree with $n+1$ vertices. We are interested in the asymptotic behavior of $X_n(k)$ for intermediate levels $k=k_n$ satisfying $k_{n}oinfty$ and $k_n=o(logn)$ as $noinfty$. In particular, we prove weak convergence of finite-dimensional distributions for the process $(X_n([k_{n}u]){)}_{u>0}$, properly normalized and centered, as $noinfty$. The limit is a centered Gaussian process with covariance $(u,v)mapsto(u+v{)}^{-1}$. One-dimensional distributional convergence of $X_n(k_n)$, properly normalized and centered, was obtained with the help of analytic tools by Fuchs, Hwang and Neininger in 2006. In contrast, our proofs which are probabilistic in nature exploit a connection of our model with certain Crump-Mode-Jagers branching processes.

Recommendations

• A functional limit theorem for the profile of random recursive trees
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• scientific article; zbMATH DE number 1180773
• On the distribution of leaves in rooted subtrees of recursive trees
• On the covariance of the level sizes in random recursive trees

Cites work

• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• A functional limit theorem for the profile of random recursive trees
• A functional limit theorem for the profile of search trees
• Asymptotics of random processes with immigration. I: Scaling limits.
• Branching processes in the analysis of the heights of trees
• Functional limit theorems for renewal shot noise processes with increasing response functions
• General Edgeworth expansions with applications to profiles of random trees
• Martingales and profile of binary search trees
• Note on the heights of random recursive trees and random m‐ary search trees
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Renewal theory for perturbed random walks and similar processes
• Stopped Random Walks
• The profile of binary search trees

Cited in

(4)

• A functional limit theorem for the profile of random recursive trees
• On the covariance of the level sizes in random recursive trees
• Limit theorems for discounted convergent perpetuities
• Weak convergence of random processes with immigration at random times

This page was built for publication: Weak convergence of the number of vertices at intermediate levels of random recursive trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4611274)