Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2018 | OriginalPaper | Chapter

Scaling Limits of Markov-Branching Trees and Applications

Lecture Notes of the XII Simposio de Probabilidad y Procesos Estocásticos 16–20 Novembre 2015, Mérida, Yucatán

Author : Bénédicte Haas

Published in: XII Symposium of Probability and Stochastic Processes

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The goal of these lecture notes is to survey some of the recent progress on the description of large-scale structure of random trees. We use the framework of Markov-Branching sequences of trees and discuss several applications.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter Optimality of Two-Parameter Strategies in Stochastic Control
Literature
1.
R. Abraham, J.-F. Delmas, Local limits of conditioned Galton-Watson trees: the condensation case. Electron. J. Probab. 19, 1–29 (2014)MathSciNetMATH
2.
R. Abraham, J.-F. Delmas, Local limits of conditioned Galton-Watson trees: the infinite spine case. Electron. J. Probab. 19, 1–19 (2014)MathSciNetMATH
3.
R. Abraham, J.-F. Delmas, P. Hoscheit, A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces. Electron. J. Probab. 18(14), 1–21 (2013)MathSciNetMATH
4.
L. Addario-Berry, N. Broutin, C. Goldschmidt, The continuum limit of critical random graphs. Probab. Theory Relat. Fields 152, 367–406 (2012)MathSciNetCrossRef
5.
L. Addario-Berry, N. Broutin, C. Holmgren, Cutting down trees with a Markov chainsaw. Ann. Appl. Probab. 24, 2297–2339 (2014)MathSciNetCrossRef
6.
L. Addario-Berry, N. Broutin, C. Goldschmidt, G. Miermont, The scaling limit of the minimum spanning tree of the complete graph. Ann. Probab. 45(5), 3075–3144 (2017)MathSciNetCrossRef
7.
M. Albenque, J.-F. Marckert, Some families of increasing planar maps. Electron. J. Probab. 13(56), 1624–1671 (2008)MathSciNetCrossRef
8.
9.
D. Aldous, The continuum random tree. II. An overview, in Stochastic Analysis (Durham, 1990). London Mathematical Society Lecture Note Series, vol. 167 (Cambridge University Press, Cambridge, 1991), pp. 23–70
10.
11.
D. Aldous, Probability distributions on cladograms, in Random Discrete Structures (Minneapolis, MN, 1993). The IMA Volumes in Mathematics and its Applications, vol. 76 (Springer, New York, 1996), pp. 1–18CrossRef
12.
J. Bertoin, Lévy Processes. Cambridge Tracts in Mathematics, vol. 121 (Cambridge University Press, Cambridge, 1996)
13.
14.
J. Bertoin, Random Fragmentation and Coagulation Processes. Cambridge Studies in Advanced Mathematics, vol. 102 (Cambridge University Press, Cambridge, 2006)
15.
16.
J. Bertoin, Sizes of the largest clusters for supercritical percolation on random recursive trees. Random Struct. Algorithm 44, 29–44 (2014)MathSciNetCrossRef
17.
18.
J. Bertoin, I. Kortchemski, Self-similar scaling limits of Markov chains on the positive integers. Ann. Appl. Probab. 26, 2556–2595 (2016)MathSciNetCrossRef
19.
J. Bertoin, G. Miermont, The cut-tree of large Galton-Watson trees and the Brownian CRT. Ann. Appl. Probab. 23, 1469–1493 (2013)MathSciNetCrossRef
20.
J. Bertoin, N. Curien, I. Kortchemski, Random planar maps & growth-fragmentations. Ann. Probab. 46(1), 207–260 (2018)MathSciNetCrossRef
21.
G. Berzunza, On scaling limits of multitype Galton-Watson trees with possibly infinite variance. Preprint (2016). arXiv:1605.04810
22.
J. Bettinelli, Scaling limit of random planar quadrangulations with a boundary. Ann. Inst. Henri Poincaré Probab. Stat. 51, 432–477 (2015)MathSciNetCrossRef
23.
P. Billingsley, Convergence of Probability Measures. Wiley Series in Probability and Statistics: Probability and Statistics, 2nd edn. (Wiley, New York, 1999). A Wiley-Interscience Publication
24.
N.H. Bingham, C.M. Goldie, J.L. Teugels, Regular Variation. Encyclopedia of Mathematics and its Applications, vol. 27 (Cambridge University Press, Cambridge, 1989)
25.
M. Bodirsky, É. Fusy, M. Kang, S. Vigerske, Boltzmann samplers, Pólya theory, and cycle pointing. SIAM J. Comput. 40, 721–769 (2011)MathSciNetCrossRef
26.
N. Broutin, P. Flajolet, The distribution of height and diameter in random non-plane binary trees. Random Struct. Algorithm 41, 215–252 (2012)MathSciNetCrossRef
27.
N. Broutin, C. Mailler, And/or trees: a local limit point of view. Random Struct. Algorithm (to appear)
28.
N. Broutin, M. Wang, Reversing the cut tree of the Brownian continuum random tree. Electron. J. Probab. 22(80), 1–23 (2017)MathSciNetMATH
29.
N. Broutin, M. Wang, Cutting down p-trees and inhomogeneous continuum random trees. Bernoulli, 23(4A), 2380–2433 (2017)MathSciNetCrossRef
30.
N. Broutin, L. Devroye, E. McLeish, M. de la Salle, The height of increasing trees. Random Struct. Algorithm 32, 494–518 (2008)MathSciNetCrossRef
31.
A. Caraceni, The scaling limit of random outerplanar maps. Ann. Inst. Henri Poincaré Probab. Stat. 52, 1667–1686 (2016)MathSciNetCrossRef
32.
B. Chen, M. Winkel, Restricted exchangeable partitions and embedding of associated hierarchies in continuum random trees. Ann. Inst. Henri Poincaré Probab. Stat. 49, 839–872 (2013)MathSciNetCrossRef
33.
B. Chen, D. Ford, M. Winkel, A new family of Markov branching trees: the alpha-gamma model. Electron. J. Probab. 14(15), 400–430 (2009)MathSciNetCrossRef
34.
35.
36.
37.
N. Curien, I. Kortchemski, Percolation on random triangulations and stable looptrees. Probab. Theory Relat. Fields 163, 303–337 (2015)MathSciNetCrossRef
38.
N. Curien, T. Duquesne, I. Kortchemski, I. Manolescu, Scaling limits and influence of the seed graph in preferential attachment trees. J. Éc. Polytech. Math. 2, 1–34 (2015)MathSciNetCrossRef
39.
N. Curien, B. Haas, I. Kortchemski, The CRT is the scaling limit of random dissections. Random Struct. Algorithms 47, 304–327 (2015)MathSciNetCrossRef
40.
L. de Raphélis, Scaling limit of multitype Galton-Watson trees with infinitely many types. Ann. Inst. Henri Poincaré Probab. Stat. 53, 200–225 (2017)MathSciNetCrossRef
41.
D. Dieuleveut, The vertex-cut-tree of Galton-Watson trees converging to a stable tree. Ann. Appl. Probab. 25, 2215–2262 (2015)MathSciNetCrossRef
42.
M. Drmota, Random Trees: An Interplay Between Combinatorics and Probability (Springer, Vienna, 2009)CrossRef
43.
44.
T. Duquesne, A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab. 31, 996–1027 (2003)MathSciNetCrossRef
45.
T. Duquesne, The exact packing measure of Lévy trees. Stoch. Process. Appl. 122, 968–1002 (2012)CrossRef
46.
T. Duquesne, J.-F. Le Gall, Random Trees, Lévy Processes and Spatial Branching Processes. Astérisque (Société Mathématique de France, Paris, 2002), pp. vi+147
47.
T. Duquesne, J.-F. Le Gall, Probabilistic and fractal aspects of Lévy trees. Probab. Theory Relat. Fields 131, 553–603 (2005)CrossRef
48.
T. Duquesne, J.-F. Le Gall, The Hausdorff measure of stable trees. ALEA Lat. Am. J. Probab. Math. Stat. 1, 393–415 (2006)MathSciNetMATH
49.
T. Duquesne, J.-F. Le Gall, On the re-rooting invariance property of Lévy trees. Electron. Commun. Probab. 14, 317–326 (2009)MathSciNetCrossRef
50.
T. Duquesne, M. Winkel, Growth of Lévy trees. Probab. Theory Relat. Fields 139, 313–371 (2007)CrossRef
51.
S.N. Evans, Probability and Real Trees. Lectures from the 35th Summer School on Probability Theory Held in Saint-Flour, July 6–23, 2005. Lecture Notes in Mathematics, vol. 1920 (Springer, Berlin, 2008)CrossRef
52.
S. Evans, J. Pitman, A. Winter, Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Relat. Fields 134(1), 918–961 (2006)MathSciNetCrossRef
53.
K. Falconer, Fractal Geometry: Mathematical Foundations and Applications, 3rd ed. (John Wiley & Sons, Chichester, 2014)MATH
54.
P. Flajolet, R. Sedgewick, Analytic Combinatorics (Cambridge University Press, Cambridge, 2009)CrossRef
55.
D. Ford, Probabilities on cladograms: introduction to the alpha model. Preprint (2005). arXiv:math/0511246
56.
57.
B. Haas, G. Miermont, The genealogy of self-similar fragmentations with negative index as a continuum random tree. Electron. J. Probab. 9(4), 57–97 (2004)MathSciNetCrossRef
58.
B. Haas, G. Miermont, Self-similar scaling limits of non-increasing Markov chains. Bernoulli J. 17, 1217–1247 (2011)MathSciNetCrossRef
59.
B. Haas, G. Miermont, Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees. Ann. Probab. 40, 2589–2666 (2012)MathSciNetCrossRef
60.
B. Haas, R. Stephenson, Scaling limits of k-ary growing trees. Ann. Inst. Henri Poincaré Probab. Stat. 51, 1314–1341 (2015)MathSciNetCrossRef
61.
B. Haas, R. Stephenson, Bivariate Markov chains converging to Lamperti transform Markov Additive Processes. Stoch. Process. Appl. (to appear)
62.
B. Haas, R. Stephenson, Multitype Markov Branching trees (In preparation)
63.
B. Haas, G. Miermont, J. Pitman, M. Winkel, Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models. Ann. Probab. 36, 1790–1837 (2008)MathSciNetCrossRef
64.
B. Haas, J. Pitman, M. Winkel, Spinal partitions and invariance under re-rooting of continuum random trees. Ann. Probab. 37, 1381–1411 (2009)MathSciNetCrossRef
65.
S. Janson, Random cutting and records in deterministic and random trees. Random Struct. Algorithms 29, 139–179 (2006)MathSciNetCrossRef
66.
S. Janson, Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation: extended abstract, in 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA’12). Discrete Mathematics and Theoretical Computer Science Proceedings, AQ (Association of Discrete Mathematics and Theoretical Computer Science, Nancy, 2012), pp. 479–490
67.
S. Janson, S.Ö. Stefánsson, Scaling limits of random planar maps with a unique large face. Ann. Probab. 43, 1045–1081 (2015)MathSciNetCrossRef
68.
A. Kolmogorov, Uber das logarithmisch normale Verteilungsgesetz der Dimensionen der Teilchen bei Zerstuckelung. C.R. Acad. Sci. U.R.S.S. 31, 99–101 (1941)
69.
I. Kortchemski, Invariance principles for Galton-Watson trees conditioned on the number of leaves. Stoch. Process. Appl. 122, 3126–3172 (2012)MathSciNetCrossRef
70.
I. Kortchemski, A simple proof of Duquesne’s theorem on contour processes of conditioned Galton-Watson trees, in Séminaire de Probabilités XLV. Lecture Notes in Mathematics, vol. 2078 (Springer, Cham, 2013), pp. 537–558
71.
72.
J.-F. Le Gall, Y. Le Jan, Branching processes in Lévy processes: the exploration process. Ann. Probab. 26, 213–252 (1998)MathSciNetCrossRef
73.
P. Marchal, A note on the fragmentation of a stable tree, in Fifth Colloquium on Mathematics and Computer Science. Discrete Mathematics and Theoretical Computer Science Proceedings, AI (Association of Discrete Mathematics and Theoretical Computer Science, Nancy, 2008), pp. 489–499
74.
J.-F. Marckert, G. Miermont, The CRT is the scaling limit of unordered binary trees. Random Struct. Algorithms 38, 467–501 (2011)MathSciNetCrossRef
75.
G. Miermont, Self-similar fragmentations derived from the stable tree. I. Splitting at heights. Probab. Theory Relat. Fields 127, 423–454 (2003)MathSciNetCrossRef
76.
G. Miermont, Self-similar fragmentations derived from the stable tree. II. Splitting at nodes. Probab. Theory Relat. Fields 131, 341–375 (2005)CrossRef
77.
G. Miermont, Invariance principles for spatial multitype Galton-Watson trees. Ann. Inst. Henri Poincaré Probab. Stat. 44, 1128–1161 (2008)MathSciNetCrossRef
78.
79.
80.
C. Pagnard, Local limits of Markov-Branching trees and their volume growth. Electron. J. Probab. 22(95), 1–53 (2017)MathSciNetMATH
81.
K. Panagiotou, B. Stufler, Scaling limits of random Pólya trees. Probab. Theory Relat. Fields 170, 801–820 (2018)CrossRef
82.
K. Panagiotou, B. Stufler, K. Weller, Scaling limits of random graphs from subcritical classes. Ann. Probab. 44, 3291–3334 (2016)MathSciNetCrossRef
83.
84.
J.L. Pavlov, The asymptotic distribution of the maximum size of trees in a random forest. Teor. Verojatnost. i Primenen. 22, 523–533 (1977)MathSciNet
85.
86.
J. Pitman, Combinatorial Stochastic Processes. Lectures from the 32nd Summer School on Probability Theory Held in Saint-Flour, July 7–24, 2002. Lecture Notes in Mathematics, vol. 1875 (Springer, Berlin, 2006)
87.
G. Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68, 145–254 (1937)CrossRef
88.
J.-L. Rémy, Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire. RAIRO Inform. Théor. 19, 179–195 (1985)MathSciNetCrossRef
89.
D. Rizzolo, Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set. Ann. Inst. Henri Poincaré Probab. Stat. 51, 512–532 (2015)MathSciNetCrossRef
90.
S. Stefánsson, The infinite volume limit of Ford’s alpha model. Acta Phys. Pol. B Proc. Suppl. 2(3), 555–560 (2009)
91.
92.
B. Stufler, The continuum random tree is the scaling limit of unlabelled unrooted trees. Preprint (2016). arXiv:1412.6333
93.
B. Stufler, Random enriched trees with applications to random graphs. Preprint (2016). arXiv:1504.02006
Metadata
Title
Scaling Limits of Markov-Branching Trees and Applications
Author
Bénédicte Haas
Copyright Year
2018
Book
XII Symposium of Probability and Stochastic Processes

Print ISBN: 978-3-319-77642-2

Electronic ISBN: 978-3-319-77643-9

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-77643-9_1