×

zbMATH — the first resource for mathematics

Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees. (English) Zbl 1259.60033
Authors’ 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.

MSC:
60F17 Functional limit theorems; invariance principles
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Aldous, D. (1985). Exchangeability and related topics. In École D’été de Probabilités de Saint-Flour , XIII- 1983. Lecture Notes in Math. 1117 1-198. Springer, Berlin. · Zbl 0562.60042
[2] Aldous, D. (1991). The continuum random tree. I. Ann. Probab. 19 1-28. · Zbl 0722.60013
[3] Aldous, D. (1991). The continuum random tree. II. An overview. In Stochastic Analysis ( Durham , 1990). London Mathematical Society Lecture Note Series 167 23-70. Cambridge Univ. Press, Cambridge. · Zbl 0791.60008
[4] Aldous, D. (1993). The continuum random tree. III. Ann. Probab. 21 248-289. · Zbl 0791.60009
[5] Aldous, D. (1996). Probability distributions on cladograms. In Random Discrete Structures ( Minneapolis , MN , 1993). The IMA Volumes in Mathematics and its Applications 76 1-18. Springer, New York. · Zbl 0841.92015
[6] Berestycki, J. (2002). Ranked fragmentations. ESAIM Probab. Stat. 6 157-175 (electronic). · Zbl 1001.60078
[7] Bertoin, J. (1996). Lévy Processes. Cambridge Tracts in Mathematics 121 . Cambridge Univ. Press, Cambridge. · Zbl 0861.60003
[8] Bertoin, J. (2002). Self-similar fragmentations. Ann. Inst. Henri Poincaré Probab. Stat. 38 319-340. · Zbl 1002.60072
[9] Bertoin, J. (2006). Random Fragmentation and Coagulation Processes. Cambridge Studies in Advanced Mathematics 102 . Cambridge Univ. Press, Cambridge. · Zbl 1107.60002
[10] Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. Wiley, New York. · Zbl 0944.60003
[11] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1989). Regular Variation. Encyclopedia of Mathematics and Its Applications 27 . Cambridge Univ. Press, Cambridge. · Zbl 0667.26003
[12] Broutin, N., Devroye, L., McLeish, E. and de la Salle, M. (2008). The height of increasing trees. Random Structures Algorithms 32 494-518. · Zbl 1148.05024
[13] Broutin, N. and Flajolet, P. (2008). The height of random binary unlabelled trees. In Fifth Colloquium on Mathematics and Computer Science . 121-134. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1250.05095
[14] Chen, B., Ford, D. and Winkel, M. (2009). A new family of Markov branching trees: The alpha-gamma model. Electron. J. Probab. 14 400-430. · Zbl 1190.60081
[15] Devroye, L. (1986). A note on the height of binary search trees. J. Assoc. Comput. Mach. 33 489-498. · Zbl 0741.05062
[16] Drmota, M. (2009). Random Trees : An Interplay Between Combinatorics and Probability . Springer, New York. · Zbl 1170.05022
[17] Drmota, M. and Gittenberger, B. (2010). The shape of unlabeled rooted random trees. European J. Combin. 31 2028-2063. · Zbl 1221.05047
[18] Duquesne, T. (2003). A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab. 31 996-1027. · Zbl 1025.60017
[19] Duquesne, T. and Le Gall, J.-F. (2002). Random trees, Lévy processes and spatial branching processes. Astérisque 281 . · Zbl 1037.60074
[20] Duquesne, T. and Le Gall, J.-F. (2005). Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields 131 553-603. · Zbl 1070.60076
[21] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes : Characterization and Convergence . Wiley, New York. · Zbl 0592.60049
[22] Evans, S. N., Pitman, J. and Winter, A. (2006). Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Related Fields 134 81-126. · Zbl 1086.60050
[23] Evans, S. N. and Winter, A. (2006). Subtree prune and regraft: A reversible real tree-valued Markov process. Ann. Probab. 34 918-961. · Zbl 1101.60054
[24] Flajolet, P. and Sedgewick, R. (2009). Analytic Combinatorics . Cambridge Univ. Press, Cambridge. · Zbl 1165.05001
[25] Haas, B. and Miermont, G. (2004). The genealogy of self-similar fragmentations with negative index as a continuum random tree. Electron. J. Probab. 9 57-97 (electronic). · Zbl 1064.60076
[26] Haas, B. and Miermont, G. (2012). Self-similar scaling limits of non-increasing Markov chains. Bernoulli 17 1217-1247. · Zbl 1263.92034
[27] Haas, B., Miermont, G., Pitman, J. and Winkel, M. (2008). Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models. Ann. Probab. 36 1790-1837. · Zbl 1155.92033
[28] Haas, B., Pitman, J. and Winkel, M. (2009). Spinal partitions and invariance under re-rooting of continuum random trees. Ann. Probab. 37 1381-1411. · Zbl 1181.60128
[29] Le Gall, J.-F. and Le Jan, Y. (1998). Branching processes in Lévy processes: The exploration process. Ann. Probab. 26 213-252. · Zbl 0948.60071
[30] Marckert, J. F. and Miermont, G. (2011). The CRT is the scaling limit of unordered binary trees. Random Structures Algorithms 38 467-501. · Zbl 1223.05027
[31] Miermont, G. (2009). Tessellations of random maps of arbitrary genus. Ann. Sci. Éc. Norm. Supér. (4) 42 725-781. · Zbl 1228.05118
[32] Otter, R. (1948). The number of trees. Ann. of Math. (2) 49 583-599. · Zbl 0032.12601
[33] Pitman, J. (2006). Combinatorial Stochastic Processes. Lecture Notes in Math. 1875 . Springer, Berlin. · Zbl 1103.60004
[34] Pitman, J. and Winkel, M. (2009). Regenerative tree growth: Binary self-similar continuum random trees and Poisson-Dirichlet compositions. Ann. Probab. 37 1999-2041. · Zbl 1189.60162
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.