Random real trees

Jean-François Le Gall[1]

  • [1] D.M.A., Ecole normale supérieure, 45 rue d’Ulm, 75005 Paris (France).

Annales de la faculté des sciences de Toulouse Mathématiques (2006)

  • Volume: 15, Issue: 1, page 35-62
  • ISSN: 0240-2963

Abstract

top
We survey recent developments about random real trees, whose prototype is the Continuum Random Tree (CRT) introduced by Aldous in 1991. We briefly explain the formalism of real trees, which yields a neat presentation of the theory and in particular of the relations between discrete Galton-Watson trees and continuous random trees. We then discuss the particular class of self-similar random real trees called stable trees, which generalize the CRT. We review several important results concerning stable trees, including their branching property, which is analogous to the well-known property of Galton-Watson trees, and the calculation of their fractal dimension. We then consider spatial trees, which combine the genealogical structure of a real tree with spatial displacements, and we explain their connections with superprocesses. In the last section, we deal with a particular conditioning problem for spatial trees, which is closely related to asymptotics for random planar quadrangulations.

How to cite

top

Le Gall, Jean-François. "Random real trees." Annales de la faculté des sciences de Toulouse Mathématiques 15.1 (2006): 35-62. <http://eudml.org/doc/10035>.

@article{LeGall2006,
abstract = {We survey recent developments about random real trees, whose prototype is the Continuum Random Tree (CRT) introduced by Aldous in 1991. We briefly explain the formalism of real trees, which yields a neat presentation of the theory and in particular of the relations between discrete Galton-Watson trees and continuous random trees. We then discuss the particular class of self-similar random real trees called stable trees, which generalize the CRT. We review several important results concerning stable trees, including their branching property, which is analogous to the well-known property of Galton-Watson trees, and the calculation of their fractal dimension. We then consider spatial trees, which combine the genealogical structure of a real tree with spatial displacements, and we explain their connections with superprocesses. In the last section, we deal with a particular conditioning problem for spatial trees, which is closely related to asymptotics for random planar quadrangulations.},
affiliation = {D.M.A., Ecole normale supérieure, 45 rue d’Ulm, 75005 Paris (France).},
author = {Le Gall, Jean-François},
journal = {Annales de la faculté des sciences de Toulouse Mathématiques},
language = {eng},
number = {1},
pages = {35-62},
publisher = {Université Paul Sabatier, Toulouse},
title = {Random real trees},
url = {http://eudml.org/doc/10035},
volume = {15},
year = {2006},
}

TY - JOUR
AU - Le Gall, Jean-François
TI - Random real trees
JO - Annales de la faculté des sciences de Toulouse Mathématiques
PY - 2006
PB - Université Paul Sabatier, Toulouse
VL - 15
IS - 1
SP - 35
EP - 62
AB - We survey recent developments about random real trees, whose prototype is the Continuum Random Tree (CRT) introduced by Aldous in 1991. We briefly explain the formalism of real trees, which yields a neat presentation of the theory and in particular of the relations between discrete Galton-Watson trees and continuous random trees. We then discuss the particular class of self-similar random real trees called stable trees, which generalize the CRT. We review several important results concerning stable trees, including their branching property, which is analogous to the well-known property of Galton-Watson trees, and the calculation of their fractal dimension. We then consider spatial trees, which combine the genealogical structure of a real tree with spatial displacements, and we explain their connections with superprocesses. In the last section, we deal with a particular conditioning problem for spatial trees, which is closely related to asymptotics for random planar quadrangulations.
LA - eng
UR - http://eudml.org/doc/10035
ER -

References

top
  1. D. Aldous, The continuum random tree I, Ann. Probab. 19 (1991), 1-28 Zbl0722.60013MR1085326
  2. D. Aldous, The continuum random tree. II. An overview, Stochastic analysis (Durham, 1990) 167 (1991), 23-70, Cambridge Univ. Press, Cambridge Zbl0791.60008MR1166406
  3. D. Aldous, The continuum random tree III, Ann. Probab. 21 (1993), 248-289 Zbl0791.60009MR1207226
  4. D. Aldous, Tree-based models for random distribution of mass, J. Stat. Phys. 73 (1993), 625-641 Zbl1102.60318MR1251658
  5. D. Aldous, Brownian excursion conditioned on its local time, Electr. Comm. Probab. 3 (1998), 79-90 Zbl0914.60049MR1650567
  6. D. Aldous, G. Miermont, J. Pitman, The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identity, Probab. Th. Rel. Fields 129 (2004), 182-218 Zbl1056.60011MR2063375
  7. J. Bennies, G. Kersting, A random walk approach to Galton-Watson trees, J. Theoret. Probab. 113 (2000), 777-803 Zbl0977.60083MR1785529
  8. M. Bousquet-Mélou, Limit laws for embedded trees. Applications to the integrated super-Brownian excursion, (2005) Zbl1107.60302
  9. J. Bouttier, P. Di Francesco, E. Guitter, Geodesic distance in planar graphs, Nuclear Phys. B 663 (2003), 535-567 Zbl1022.05022MR1987861
  10. J. Bouttier, P. Di Francesco, E. Guitter, Statistics of planar graphs viewed from a vertex: a study via labeled trees, Nuclear Phys. B 675 (2003), 631-660 Zbl1027.05021MR2018892
  11. J. Bouttier, P. Di Francesco, E. Guitter, Planar maps as labeled mobiles, Electronic J. Combinatorics 11 (2004) Zbl1060.05045MR2097335
  12. N.G. De Bruijn, D.E. Knuth, S.O. Rice, The average height of planted plane trees, Graph theory and computing (1972), 15-22, Academic Press, New York Zbl0247.05106MR505710
  13. P. Chassaing, G. Schaeffer, Random planar lattices and integrated superBrownian excursion, Probab. Th. Rel. Fields 128 (2004), 161-212 Zbl1041.60008MR2031225
  14. K.L. Chung, Excursions in Brownian motion, Ark. Mat. 14 (1976), 155-177 Zbl0356.60033MR467948
  15. D.A. Dawson, E.A. Perkins, Historical Processes, Memoirs Amer. Math. Soc. 454 (1991) Zbl0754.60062MR1079034
  16. J.F. Delmas, Computation of moments for the length of the one dimensional ISE support, Electron. J. Probab. 8 (2003) Zbl1064.60169MR2041818
  17. E. Derbez, G. Slade, The scaling limit of lattice trees in high dimensions, Comm. Math. Phys. 198 (1998), 69-104 Zbl0915.60076MR1620301
  18. A. Dress, V. Moulton, W. Terhalle, T -theory: An overview, Europ. J. Combinatorics 17 (1996), 161-175 Zbl0853.54027MR1379369
  19. M. Drmota, B. Gittenberger, On the profile of random trees, Random Structures Algorithms 10 (1997), 321-451 Zbl0882.60084MR1608230
  20. T. Duquesne, A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab. 31 (2003), 996-1027 Zbl1025.60017MR1964956
  21. T. Duquesne, J.-F. Le Gall, Random trees, Lévy processes and spatial branching processes, Astérisque 281 (2002) Zbl1037.60074MR1954248
  22. T. Duquesne, J.-F. Le Gall, Probabilistic and fractal aspects of Lévy trees, Probab. Th. Rel. Fields 131 (2005), 553-603 Zbl1070.60076MR2147221
  23. T. Duquesne, J.-F. Le Gall, The Hausdorff measure of stable trees, (2005) Zbl1128.60072
  24. B. Durhuus, Probabilistic aspects of infinite trees and surfaces, Acta Physica Polonica B 34 (2003), 4795-4811 
  25. E.B. Dynkin, A probabilistic approach to one class of nonlinear differential equations, Probab. Th. Rel. Fields 89 (1991), 89-115 Zbl0722.60062MR1109476
  26. E.B. Dynkin, S.E. Kuznetsov, ℕ -measures for branching exit Markov systems and their applications to differential equations, Probab. Theory Related Fields 130 (2004), 135-150 Zbl1068.31002MR2092876
  27. S.N. Evans, J.W. Pitman, A. Winter, Rayleigh processes, real trees and root growth with re-grafting, (2003) Zbl1086.60050
  28. S.N. Evans, A. Winter, Subtree prune and re-graft: A reversible real tree valued Markov process, (2005) 
  29. P. Flajolet, A.M Odlyzko, The average height of binary trees and other simple trees, J. Comput. Systs. Sci. 25 (1982), 171-213 Zbl0499.68027MR680517
  30. J. Geiger, L. Kauffmann, The shape of large Galton-Watson trees with possibly infinite variance, Random Structures Algorithms 25 (2004), 311-335 Zbl1071.60078MR2086163
  31. Geiger J., G. Kersting, The Galton-Watson tree conditioned on its height, Proceedings 7th Vilnius Conference 1998 (1999), 277-286, GrigelionisB.B. Zbl1021.60065
  32. M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, (1999), Birkhäuser, Boston Zbl0953.53002MR1699320
  33. B. Haas, G. Miermont, The genealogy of self-similar fragmentations with negative index as a continuum random tree, Electron. J. Probab. 9 (2004), 57-97 (electronic) Zbl1064.60076MR2041829
  34. T. Hara, G. Slade, The scaling limit of the incipient infinite cluster in high-dimensional percolation. II. Integrated super-Brownian excursion. Probabilistic techniques in equilibrium and nonequilibrium statistical physics, J. Math. Phys. 41 (2000), 1244-1293 Zbl0977.82022MR1757958
  35. R. van der Hofstad, G. Slade, Convergence of critical oriented percolation to super-Brownian motion above 4 + 1 dimensions, Ann. Inst. H. Poincaré Probab. Statist. 20 (2003), 413-485 Zbl1020.60099MR1978987
  36. K. Itô, H.P. McKean, Diffusion Processes and their Sample Paths, (1965), Academic Press Inc., Publishers, New York Zbl0285.60063MR199891
  37. D.P. Kennedy, The distribution of the maximum Brownian excursion, J. Appl. Probab. 13 (1976), 371-376 Zbl0338.60048MR402955
  38. H. Kesten, Branching random walk with a critical branching part, J. Theoret. Probability 8 (1995), 921-962 Zbl0857.60087MR1353560
  39. S. Janson, J.F. Marckert, Convergence of discrete snakes, J. Theoret. Probab. 18 (2005), 615-647 Zbl1084.60049MR2167644
  40. J. Lamperti, The limit of a sequence of branching processes, Z. Wahrsch. verw. Gebiete 7 (1967), 271-288 Zbl0154.42603MR217893
  41. M. Ledoux, M. Talagrand, Probability in Banach Spaces, (1991), Springer, Berlin Zbl0748.60004MR1102015
  42. J.F. Le Gall, Brownian excursions, trees and measure-valued branching processes, Ann. Probab. 19 (1991), 1399-1439 Zbl0753.60078MR1127710
  43. J.F. Le Gall, A class of path-valued Markov processes and its applications to superprocesses, Probab. Th. Rel. Fields 96 (1993), 25-46 Zbl0794.60076MR1207305
  44. J.F. Le Gall, The Brownian snake and solutions of Δ u = u 2 in a domain, Probab. Th. Rel. Fields 102 (1995), 393-432 Zbl0826.60062MR1339740
  45. J.F. Le Gall, Spatial Branching Processes, Random Snakes and Partial Differential Equations, Lectures in Mathematics ETH Zürich (1999), Birkhäuser, Boston Zbl0938.60003MR1714707
  46. J.F. Le Gall, An invariance principle for conditioned trees, (2005) 
  47. J.F. Le Gall, Y. Le Jan, Branching processes in Lévy processes: The exploration process, Ann. Probab. 26 (1998), 213-252 Zbl0948.60071MR1617047
  48. J.F. Le Gall, Y. Le Jan, Branching processes in Lévy processes: Laplace functionals of snakes and superprocesses, Probab. 26 (1998), 1407-1432 Zbl0945.60090MR1675019
  49. J.F. Le Gall, E.A. Perkins, The Hausdorff measure of the support of two-dimensional super-Brownian motion, Ann. Probab. 23 (1995), 1719-1747 Zbl0856.60055MR1379165
  50. J.F. Le Gall, M. Weill, Conditioned Brownian trees, Ann. Institut H. Poincaré, to appear (2004) Zbl1107.60053
  51. J.F. Marckert, A. Mokkadem, The depth first processes of Galton-Watson processes converge to the same Brownian excursion, Ann. Probab. 31 (2003), 1655-1678 Zbl1049.05026MR1989446
  52. J.F. Marckert, A. Mokkadem, Limits of normalized quadrangulations. The Brownian map. Preprint, (2004) Zbl1117.60038
  53. G. Miermont, Self-similar fragmentations derived from the stable tree: Spliting at heights, Probab. Th. Rel. Fields 127 (2003), 423-454 Zbl1042.60043MR2018924
  54. J. Neveu, Arbres et processus de Galton-Watson, Ann. Inst. Henri Poincaré 22 (1986), 199-207 Zbl0601.60082MR850756
  55. F. Paulin, The Gromov topology on ℝ -trees, Topology Appl. 32 (1989), 197-221 Zbl0675.20033MR1007101
  56. E.A. Perkins, A space-time property of a class of measure-valued branching diffusions, Trans. Amer. Math. Soc. 305 (1988), 743-795 Zbl0641.60060MR924777
  57. J. Pitman, The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest, Ann. Probab. 27 (1999), 261-283 Zbl0954.60060MR1681110
  58. J. Pitman, Combinatorial stochastic processes, (2002) Zbl1103.60004MR1897932
  59. D. Revuz, M. Yor, Continuous Martingales and Brownian Motion, (1991), Springer, Berlin-Heidelberg-New York Zbl0731.60002MR1083357
  60. W. Vervaat, A relation between Brownian bridge and Brownian excursion, Ann. Probab. 10 (1982), 234-239 MR515820

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.