Random real trees

Le Gall, Jean-François

Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 15 (2006) no. 1, pp. 35-62.

Nous discutons certains développements récents de la théorie des arbres réels aléatoires, dont le prototype est le CRT introduit par Aldous en 1991. Nous introduisons le formalisme d’arbre réel, qui fournit une présentation élégante de la théorie, et en particulier des relations entre les arbres de Galton-Watson discrets et les arbres continus aléatoires. Nous discutons ensuite la classe des arbres auto-similaires appelés arbres stables, qui généralisent le CRT. Nous présentons plusieurs résultats importants au sujet des arbres stables, notamment leur propriété de branchement, analogue continu d’une propriété bien connue pour les arbres de Galton-Watson, et le calcul de leurs dimensions fractales. Nous considérons ensuite les arbres spatiaux, qui combinent la structure généalogique d’un arbre réel avec des déplacements dans l’espace, et nous expliquons leurs liens avec les superprocessus. Dans la dernière partie, nous traitons un conditionnement particulier des arbres spatiaux, qui est étroitement lié à certains résultats asymptotiques pour les quadrangulations planes aléatoires.

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.

[1] Aldous, D. The continuum random tree I, Ann. Probab., Volume 19 (1991), pp. 1-28 | MR | Zbl

[2] Aldous, D. The continuum random tree. II. An overview, Stochastic analysis (Durham, 1990) (London Math. Soc. Lecture Note Ser.), Volume 167, Cambridge Univ. Press, Cambridge, 1991, pp. 23-70 | MR | Zbl

[3] Aldous, D. The continuum random tree III, Ann. Probab., Volume 21 (1993), pp. 248-289 | MR | Zbl

[4] Aldous, D. Tree-based models for random distribution of mass, J. Stat. Phys., Volume 73 (1993), pp. 625-641 | MR | Zbl

[5] Aldous, D. Brownian excursion conditioned on its local time, Electr. Comm. Probab., Volume 3 (1998), pp. 79-90 | MR | Zbl

[6] Aldous, D.; Miermont, G.; Pitman, J. The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identity, Probab. Th. Rel. Fields, Volume 129 (2004), pp. 182-218 | MR | Zbl

[7] Bennies, J.; Kersting, G. A random walk approach to Galton-Watson trees, J. Theoret. Probab., Volume 113 (2000), pp. 777-803 | MR | Zbl

[8] Bousquet-Mélou, M. Limit laws for embedded trees. Applications to the integrated super-Brownian excursion (2005) (Preprint, arXiv:math.CO/0501266)

[9] Bouttier, J.; Di Francesco, P.; Guitter, E. Geodesic distance in planar graphs, Nuclear Phys. B, Volume 663 (2003), pp. 535-567 | MR | Zbl

[10] Bouttier, J.; Di Francesco, P.; Guitter, E. Statistics of planar graphs viewed from a vertex: a study via labeled trees, Nuclear Phys. B, Volume 675 (2003), pp. 631-660 | MR | Zbl

[11] Bouttier, J.; Di Francesco, P.; Guitter, E. Planar maps as labeled mobiles, Electronic J. Combinatorics, Volume 11 (2004), pp. Research Paper 69, 27 pp. (electronic) | MR | Zbl

[12] De Bruijn, N.G.; Knuth, D.E.; Rice, S.O. The average height of planted plane trees, Graph theory and computing, Academic Press, New York, 1972, pp. 15-22 | MR | Zbl

[13] Chassaing, P.; Schaeffer, G. Random planar lattices and integrated superBrownian excursion, Probab. Th. Rel. Fields, Volume 128 (2004), pp. 161-212 | MR | Zbl

[14] Chung, K.L. Excursions in Brownian motion, Ark. Mat., Volume 14 (1976), pp. 155-177 | MR | Zbl

[15] Dawson, D.A.; Perkins, E.A. Historical Processes, Memoirs Amer. Math. Soc., Volume 454 (1991), pp. iv+179 | MR | Zbl

[16] Delmas, J.F. Computation of moments for the length of the one dimensional ISE support, Electron. J. Probab., Volume 8 (2003) no. 17, pp. 15 pp. (electronic) | MR | Zbl

[17] Derbez, E.; Slade, G. The scaling limit of lattice trees in high dimensions, Comm. Math. Phys., Volume 198 (1998), pp. 69-104 | MR | Zbl

[18] Dress, A.; Moulton, V.; Terhalle, W. $T$-theory: An overview, Europ. J. Combinatorics, Volume 17 (1996), pp. 161-175 | MR | Zbl

[19] Drmota, M.; Gittenberger, B. On the profile of random trees, Random Structures Algorithms, Volume 10 (1997), pp. 321-451 | MR | Zbl

[20] Duquesne, T. A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab., Volume 31 (2003), pp. 996-1027 | MR | Zbl

[21] Duquesne, T.; Le Gall, J.-F. Random trees, Lévy processes and spatial branching processes, Astérisque, Volume 281 (2002), pp. vi+147 | Numdam | MR | Zbl

[22] Duquesne, T.; Le Gall, J.-F. Probabilistic and fractal aspects of Lévy trees, Probab. Th. Rel. Fields, Volume 131 (2005), pp. 553-603 | MR | Zbl

[23] Duquesne, T.; Le Gall, J.-F. The Hausdorff measure of stable trees (2005) (In preparation)

[24] Durhuus, B. Probabilistic aspects of infinite trees and surfaces, Acta Physica Polonica B, Volume 34 (2003), pp. 4795-4811

[25] Dynkin, E.B. A probabilistic approach to one class of nonlinear differential equations, Probab. Th. Rel. Fields, Volume 89 (1991), pp. 89-115 | MR | Zbl

[26] Dynkin, E.B.; Kuznetsov, S.E. $\mathbb{N}$-measures for branching exit Markov systems and their applications to differential equations, Probab. Theory Related Fields, Volume 130 (2004) no. 1, pp. 135-150 | MR | Zbl

[27] Evans, S.N.; Pitman, J.W.; Winter, A. Rayleigh processes, real trees and root growth with re-grafting (2003) (48 Pages. Minor revision of version of Feb 2004. To appear in Probab. Th. and Rel. Fields) | Zbl

[28] Evans, S.N.; Winter, A. Subtree prune and re-graft: A reversible real tree valued Markov process (2005) (Preprint, arXiv:math.PR/05022266)

[29] Flajolet, P.; Odlyzko, A.M The average height of binary trees and other simple trees, J. Comput. Systs. Sci., Volume 25 (1982) no. 2, pp. 171-213 | MR | Zbl

[30] Geiger, J.; Kauffmann, L. The shape of large Galton-Watson trees with possibly infinite variance, Random Structures Algorithms, Volume 25 (2004), pp. 311-335 | MR | Zbl

[31] J., Geiger; Kersting, G.; Grigelionis, B. The Galton-Watson tree conditioned on its height, Proceedings 7th Vilnius Conference 1998 (1999), pp. 277-286 (VSP) | Zbl

[32] Gromov, M. Metric Structures for Riemannian and Non-Riemannian Spaces, Birkhäuser, Boston, 1999 | MR | Zbl

[33] Haas, B.; Miermont, G. The genealogy of self-similar fragmentations with negative index as a continuum random tree, Electron. J. Probab., Volume 9 (2004) no. 4, p. 57-97 (electronic) | MR | Zbl

[34] Hara, T.; Slade, G. 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., Volume 41 (2000), pp. 1244-1293 | MR | Zbl

[35] van der Hofstad, R.; Slade, G. Convergence of critical oriented percolation to super-Brownian motion above $4+1$ dimensions, Ann. Inst. H. Poincaré Probab. Statist., Volume 20 (2003), pp. 413-485 | Numdam | MR | Zbl

[36] Itô, K.; McKean, H.P. Diffusion Processes and their Sample Paths, Die Grundlehren der Mathematischen Wissenschaften, Band 125, Academic Press Inc., Publishers, New York, 1965 | MR | Zbl

[37] Kennedy, D.P. The distribution of the maximum Brownian excursion, J. Appl. Probab., Volume 13 (1976), pp. 371-376 | MR | Zbl

[38] Kesten, H. Branching random walk with a critical branching part, J. Theoret. Probability, Volume 8 (1995), pp. 921-962 | MR | Zbl

[39] Janson, S.; Marckert, J.F. Convergence of discrete snakes, J. Theoret. Probab., Volume 18 (2005) no. 3, pp. 615-647 | MR | Zbl

[40] Lamperti, J. The limit of a sequence of branching processes, Z. Wahrsch. verw. Gebiete, Volume 7 (1967), pp. 271-288 | MR | Zbl

[41] Ledoux, M.; Talagrand, M. Probability in Banach Spaces, Springer, Berlin, 1991 | MR | Zbl

[42] Le Gall, J.F. Brownian excursions, trees and measure-valued branching processes, Ann. Probab., Volume 19 (1991), pp. 1399-1439 | MR | Zbl

[43] Le Gall, J.F. A class of path-valued Markov processes and its applications to superprocesses, Probab. Th. Rel. Fields, Volume 96 (1993), pp. 25-46 | MR | Zbl

[44] Le Gall, J.F. The Brownian snake and solutions of $\Delta u=u^2$ in a domain, Probab. Th. Rel. Fields, Volume 102 (1995), pp. 393-432 | MR | Zbl

[45] Le Gall, J.F. Spatial Branching Processes, Random Snakes and Partial Differential Equations, Lectures in Mathematics ETH Zürich, Birkhäuser, Boston, 1999 | MR | Zbl

[46] Le Gall, J.F. An invariance principle for conditioned trees (2005) (Preprint)

[47] Le Gall, J.F.; Le Jan, Y. Branching processes in Lévy processes: The exploration process, Ann. Probab., Volume 26 (1998), pp. 213-252 | MR | Zbl

[48] Le Gall, J.F.; Le Jan, Y. Branching processes in Lévy processes: Laplace functionals of snakes and superprocesses, Probab., Volume 26 (1998), pp. 1407-1432 | MR | Zbl

[49] Le Gall, J.F.; Perkins, E.A. The Hausdorff measure of the support of two-dimensional super-Brownian motion, Ann. Probab., Volume 23 (1995), pp. 1719-1747 | MR | Zbl

[50] Le Gall, J.F.; Weill, M. Conditioned Brownian trees, Ann. Institut H. Poincaré, to appear, 2004 (arXiv:math.PR/0501066)

[51] Marckert, J.F.; Mokkadem, A. The depth first processes of Galton-Watson processes converge to the same Brownian excursion, Ann. Probab., Volume 31 (2003), pp. 1655-1678 | MR | Zbl

[52] Marckert, J.F.; Mokkadem, A. Limits of normalized quadrangulations. The Brownian map. Preprint (2004) (arXiv:math.PR/0403398)

[53] Miermont, G. Self-similar fragmentations derived from the stable tree: Spliting at heights, Probab. Th. Rel. Fields, Volume 127 (2003), pp. 423-454 | MR | Zbl

[54] Neveu, J. Arbres et processus de Galton-Watson, Ann. Inst. Henri Poincaré, Volume 22 (1986), pp. 199-207 | Numdam | MR | Zbl

[55] Paulin, F. The Gromov topology on $ℝ$-trees, Topology Appl., Volume 32 (1989), pp. 197-221 | MR | Zbl

[56] Perkins, E.A. A space-time property of a class of measure-valued branching diffusions, Trans. Amer. Math. Soc., Volume 305 (1988), pp. 743-795 | MR | Zbl

[57] Pitman, J. 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., Volume 27 (1999), pp. 261-283 | MR | Zbl

[58] Pitman, J. Combinatorial stochastic processes (2002) (Lectures from the Saint-Flour probability summer school. To appear) | MR | Zbl

[59] Revuz, D.; Yor, M. Continuous Martingales and Brownian Motion, Springer, Berlin-Heidelberg-New York, 1991 | MR | Zbl

[60] Vervaat, W. A relation between Brownian bridge and Brownian excursion, Ann. Probab., Volume 10 (1982), pp. 234-239 | MR