The Continuum Random Tree. I
David Aldous · The Annals of Probability · 1991
Exact and asymptotic results for the uniform random labelled tree on $n$ vertices have been studied extensively by combinatorialists. Here we treat asymptotics from a modern stochastic process viewpoint. There are three limit processes. One is an infinite discrete tree. The other two are most naturally represented as continuous two-dimensional fractal tree-like subsets of the infinite-dimensional space $l_1$. One is compact; the other is unbounded and self-similar. The proofs are based upon a simple algorithm for generating the finite random tree and upon weak convergence arguments. Distributional properties of these limit processes will be discussed in a sequel.
Cited by 812 works. doi:10.1214/aop/1176990534 Open-access PDF
Authors
References
- Stochastic processes
- Convergence of Probability Measures
- Real Analysis and Probability.
- Counting labelled trees
- On the height of trees
- On the Altitude of Nodes in Random Trees
- The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
- The average height of binary trees and other simple trees
- Brownian Excursions, Trees and Measure-Valued Branching Processes
- Random labelled trees and their branching networks