Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees

Abstract

We consider a family of random trees satisfying a Markov branching property. Roughly, this property says that the subtrees above some given height are independent with a law that depends only on their total size, the latter being either the number of leaves or vertices. Such families are parameterized by sequences of distributions on partitions of the integers that determine how the size of a tree is distributed in its different subtrees. Under some natural assumption on these distributions, stipulating that "macroscopic" splitting events are rare, we show that Markov branching trees admit the so-called self-similar fragmentation trees as scaling limits in the Gromov-Hausdorff-Prokhorov topology. The main application of these results is that the scaling limit of random uniform unordered trees is the Brownian continuum random tree. This extends a result by Marckert-Miermont and fully proves a conjecture by Aldous. We also recover, and occasionally extend, results on scaling limits of consistent Markov branching models and known convergence results of Galton-Watson trees toward the Brownian and stable continuum random trees.

Published in at http://dx.doi.org/10.1214/11-AOP686 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (7)

• Spinal partitions and invariance under re-rooting of continuum random trees
• Subtree prune and regraft: a reversible real tree-valued Markov process
• Ranked Fragmentations
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models
• Self-similar scaling limits of non-increasing Markov chains
• A limit theorem for the contour process of conditioned Galton-Watson trees
• Regenerative tree growth: Binary self-similar continuum random trees and Poisson--Dirichlet compositions

Cited by in corpus (27)

• Scaling limits of random trees and planar maps
• The gap between Gromov-vague and Gromov-Hausdorff-vague topology
• Cutting down trees with a Markov chainsaw
• Self-similar scaling limits of non-increasing Markov chains
• Subsequential scaling limits of simple random walk on the two-dimensional uniform spanning tree
• The cut-tree of large Galton-Watson trees and the Brownian CRT
• Regenerative tree growth: Markovian embedding of fragmenters, bifurcators, and bead splitting processes
• The continuum random tree is the scaling limit of unlabelled unrooted trees
• Tree limits and limits of random trees
• Cutting edges at random in large recursive trees
• The dual tree of a recursive triangulation of the disk
• Schröder's problems and scaling limits of random trees
• Scaling limits of stochastic processes associated with resistance forms
• Markov branching in the vertex splitting model
• Scaling limits of slim and fat trees
• Regenerative tree growth: structural results and convergence
• A line-breaking construction of the stable trees
• Entropy and Hausdorff Dimension in Random Growing Trees
• Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees
• Scaling limits for some random trees constructed inhomogeneously
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of n-leaf Galton-Watson trees
• The Brownian continuum random tree as the unique solution to a fixed point equation
• The degree profile of Pólya trees
• Limiting Behavior Of Additive Functionals On The Stable Tree
• The stable trees are nested
• Cutting down $\mathbf{p}$-trees and inhomogeneous continuum random trees
• Almost sure convergence of vertex degree densities in the vertex-splitting model