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

DOI10.1214/11-AOP686MaRDI QIDQ693717zbMATH OpenFDO

Authors Bénédicte Haas, Grégory Miermont

Publication date 10 December 2012

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.3632, https://projecteuclid.org/euclid.aop/1351258735

zbMATH Keywords

scaling limitsself-similar fragmentationsrandom treescontinuum random treesMarkov branching property

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

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.

Recommendations

• Scaling Limits of Markov-Branching Trees and Applications
• Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
• Scaling limits of multi-type Markov branching trees
• Scaling limits of tree-valued branching random walks
• A note on the scaling limits of contour functions of Galton-Watson trees
• A uniform limit law for the branching measure on a Galton-Watson tree
• Limit theorems for Markov processes indexed by continuous time Galton-Watson trees
• On scaling limits of multitype Galton-Watson trees with possibly infinite variance
• Scaling limit of random \(k\)-trees
• Scaling limits of random trees and random graphs

Cites work

• scientific article; zbMATH DE number 3896009 (Why is no real title available?)
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 43570 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1859371 (Why is no real title available?)
• scientific article; zbMATH DE number 850224 (Why is no real title available?)
• scientific article; zbMATH DE number 918811 (Why is no real title available?)
• A limit theorem for the contour process of conditioned Galton-Watson trees
• A new family of Markov branching trees: the alpha-gamma model
• A note on the height of binary search trees
• Analytic combinatorics
• Branching processes in Lévy processes: The exploration process
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
• Probabilistic and fractal aspects of Lévy trees
• Random Fragmentation and Coagulation Processes
• Random Trees
• Ranked Fragmentations
• Rayleigh processes, real trees, and root growth with re-grafting
• Regenerative tree growth: binary self-similar continuum random trees and Poisson-Dirichlet compositions
• Self-similar fragmentations
• Self-similar scaling limits of non-increasing Markov chains
• Spinal partitions and invariance under re-rooting of continuum random trees
• Subtree prune and regraft: a reversible real tree-valued Markov process
• Tessellations of random maps of arbitrary genus
• The CRT is the scaling limit of unordered binary trees
• The continuum random tree. I
• The continuum random tree. III
• The distribution of height and diameter in random non-plane binary trees
• The genealogy of self-similar fragmentations with negative index as a continuum random tree
• The height of increasing trees
• The number of trees
• The shape of unlabeled rooted random trees

Cited in

(67)

• Cutoff on trees is rare
• Sizes of the largest clusters for supercritical percolation on random recursive trees
• Scaling limits of slim and fat trees
• Poisson point process limits in size-biased Galton-Watson trees
• The CRT is the scaling limit of random dissections
• Limits of random tree-like discrete structures
• Cutting edges at random in large recursive trees
• The dual tree of a recursive triangulation of the disk
• Scaling limits for a family of unrooted trees
• On the Wiener index of random trees
• Multicritical continuous random trees
• Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees
• Bivariate Markov chains converging to Lamperti transform Markov additive processes
• The shape of unlabeled rooted random trees
• Inverting the cut-tree transform
• Scaling Limits of Markov-Branching Trees and Applications
• Recursive construction of continuum random trees
• The CRT is the scaling limit of unordered binary trees
• Forward-backward stochastic differential equations and controlled McKean-Vlasov dynamics
• Zooming in at the root of the stable tree
• An asymptotic analysis of labeled and unlabeled k-trees
• Dissecting the circle, at random
• Scaling limits of multi-type Markov branching trees
• The scaling limit of a critical random directed graph
• Self-similar scaling limits of non-increasing Markov chains
• The cut-tree of large Galton-Watson trees and the Brownian CRT
• Scaling limit of critical random trees in random environment
• Cutting down trees with a Markov chainsaw
• Consistent Markov branching trees with discrete edge lengths
• Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
• Graphon convergence of random cographs
• Generalized Markov branching trees
• A binary embedding of the stable line-breaking construction
• Tail asymptotics for extinction times of self-similar fragmentations
• The degree profile of random Pólya trees
• Self-similar growth fragmentations as scaling limits of Markov branching processes
• Invariance principle for fragmentation processes derived from conditioned stable Galton-Watson trees
• Almost sure convergence of vertex degree densities in the vertex splitting model
• Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees
• On random trees and forests
• Scaling limits of stochastic processes associated with resistance forms
• Simply generated unrooted plane trees
• Scaling limits of k-ary growing trees
• Probability, trees and algorithms. Abstracts from the workshop held November 2--8, 2014.
• Surprising identities for the greedy independent set on Cayley trees
• Scaling limits and influence of the seed graph in preferential attachment trees
• Local limits of Markov branching trees and their volume growth
• Graph limits of random graphs from a subset of connected \(k\)-trees
• Stable graphs: distributions and line-breaking construction
• Fires on trees
• Scaling limits of random Pólya trees
• Scaling limits for some random trees constructed inhomogeneously
• Cutting down \(\mathbf{p}\)-trees and inhomogeneous continuum random trees
• The gap between Gromov-Vague and Gromov-Hausdorff-vague topology
• The continuum random tree. III
• Schröder's problems and scaling limits of random trees
• Growing random graphs with a preferential attachment structure
• A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees
• Tree limits and limits of random trees
• The cut-tree of large recursive trees
• Excursion theory for Brownian motion indexed by the Brownian tree
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson trees
• Random enriched trees with applications to random graphs
• The stable trees are nested
• A down‐up chain with persistent labels on multifurcating trees
• The distribution of height and diameter in random non-plane binary trees
• Scaling limits for simple random walks on random ordered graph trees

This page was built for publication: Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees

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