A functional limit theorem for the profile of random recursive trees

DOI10.1214/18-ECP188MaRDI QIDQ1725478zbMATH OpenFDO

Authors Zakhar Kabluchko, Alexander Iksanov

Publication date 14 February 2019

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.04606, https://projecteuclid.org/euclid.ecp/1542942176

zbMATH Keywords

profilefunctional limit theorembranching random walkrandom recursive treeintegrated Brownian motioncrump-mode-jagers branching processlow levels

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Sums of independent random variables; random walks (60G50) Functional limit theorems; invariance principles (60F17) 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 prove a functional limit theorem for the vector-valued process $(X_{[n^t]}(1),ldots,X_{[n^t]}(k){)}_{tgeq0}$, for each $kinmathbbN$. 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.

Recommendations

• Weak convergence of the number of vertices at intermediate levels of random recursive trees
• A functional limit law for the profile of plane-oriented recursive trees
• A functional limit theorem for the profile of \(b\)-ary trees
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Random recursive trees: a boundary theory approach

Cites work

• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• A functional limit theorem for the profile of search trees
• An alternative proof of Lorden&s renewal inequality
• Analytic combinatorics
• Asymptotics of random processes with immigration. I: Scaling limits.
• Branching processes in the analysis of the heights of trees
• Degree distribution in the lower levels of the uniform recursive tree
• Functional limit theorems for renewal shot noise processes with increasing response functions
• General Edgeworth expansions with applications to profiles of random trees
• Martingales and large deviations for binary search trees
• Martingales and profile of binary search trees
• Note on the heights of random recursive trees and random m‐ary search trees
• On the moments and limit distributions of some first passage times
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Random Trees
• Renewal theory for perturbed random walks and similar processes
• Stopped Random Walks
• The profile of binary search trees

Cited in

(14)

• A limit theorem for recursively defined processes in Lp
• Normal Limit Law for Protected Node Profile of Random Recursive Trees
• Asymptotic fluctuations in supercritical Crump-Mode-Jagers processes
• Weak convergence of the number of vertices at intermediate levels of random recursive trees
• Renewal theory for iterated perturbed random walks on a general branching process tree: Early generations
• Limit theorems for random trees.
• A functional limit law for the profile of plane-oriented recursive trees
• A functional limit theorem for general shot noise processes
• Limiting distributions for additive functionals on Catalan trees
• Profile of random exponential recursive trees
• A central limit theorem for additive functionals of increasing trees
• Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Weak convergence of random processes with immigration at random times

This page was built for publication: A functional limit theorem for the profile of random recursive trees

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