zbMATH — the first resource for mathematics

Random recursive trees: a boundary theory approach. (English) Zbl 1327.60031
Summary: 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.

60C05 Combinatorial probability
05C05 Trees
60J50 Boundary theory for Markov processes
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Full Text: DOI arXiv