Random recursive trees: A boundary theory approach

2014/06/30 by Rudolf Grübel, Grübel, Rudolf, Igor Michailow +1
Computer Science · Mathematics · #60J50 #68Q87 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Primary 60C05 #Probability (math.PR) #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis #secondary 05C05

paper · pdf · doi:10.48550/arxiv.1406.7614

openalex publication_date 2014/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that an algorithmic construction of sequences of recursive trees leads to a direct proof of the convergence of random recursive trees in an associated Doob-Martin compactification; it also gives a representation of the limit in terms of the input sequence of the algorithm. We further show that this approach can be used to obtain strong limit theorems for various tree functionals, such as path length or the Wiener index.

Related

• On tail bounds for random recursive trees
• Scaling limits for some random trees constructed inhomogeneously
• Weak convergence of the number of vertices at intermediate levels of\n random recursive trees
• A functional limit theorem for the profile of random recursive trees
• Recursive construction of continuum random trees