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

DOI10.1017/JPR.2018.75zbMATH Open1405.60031arXiv1806.10872OpenAlexW2963202354WikidataQ128576641 ScholiaQ128576641MaRDI QIDQ4611274FDOQ4611274

Authors: Zakhar Kabluchko, Alexander Iksanov 

Publication date: 17 January 2019

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• The profile of binary search trees
• Functional limit theorems for renewal shot noise processes with increasing response functions
• Stopped Random Walks
• Branching processes in the analysis of the heights of trees
• Note on the heights of random recursive trees and random m‐ary search trees
• A functional limit theorem for the profile of search trees
• Martingales and profile of binary search trees
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Asymptotics of random processes with immigration. I: Scaling limits.
• A functional limit theorem for the profile of random recursive trees
• Renewal theory for perturbed random walks and similar processes
• General Edgeworth expansions with applications to profiles of random 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)