Feuilleter
no. 1
Random real trees
Jean-François Le Gall1
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, 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.

DOI : 10.5802/afst.1112

Jean-François Le Gall 1

1 D.M.A., Ecole normale supérieure, 45 rue d’Ulm, 75005 Paris (France). 
@article{AFST_2006_6_15_1_35_0,
     author = {Jean-Fran\c{c}ois Le Gall},
     title = {Random real trees},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {35--62},
     publisher = {Universit\'e Paul Sabatier, Institut de Math\'ematiques},
     address = {Toulouse},
     volume = {Ser. 6, 15},
     number = {1},
     year = {2006},
     doi = {10.5802/afst.1112},
     mrnumber = {2225746},
     zbl = {1129.60047},
     language = {en},
     url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1112/}
}
TY  - JOUR
AU  - Jean-François Le Gall
TI  - Random real trees
JO  - Annales de la Faculté des sciences de Toulouse : Mathématiques
PY  - 2006
SP  - 35
EP  - 62
VL  - 15
IS  - 1
PB  - Université Paul Sabatier, Institut de Mathématiques
PP  - Toulouse
UR  - https://afst.centre-mersenne.org/articles/10.5802/afst.1112/
DO  - 10.5802/afst.1112
LA  - en
ID  - AFST_2006_6_15_1_35_0
ER  - 
%0 Journal Article
%A Jean-François Le Gall
%T Random real trees
%J Annales de la Faculté des sciences de Toulouse : Mathématiques
%D 2006
%P 35-62
%V 15
%N 1
%I Université Paul Sabatier, Institut de Mathématiques
%C Toulouse
%U https://afst.centre-mersenne.org/articles/10.5802/afst.1112/
%R 10.5802/afst.1112
%G en
%F AFST_2006_6_15_1_35_0
Jean-François Le Gall. Random real trees. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 15 (2006) no. 1, pp. 35-62. doi : 10.5802/afst.1112. https://afst.centre-mersenne.org/articles/10.5802/afst.1112/

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

[2] D. Aldous 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] D. Aldous The continuum random tree III, Ann. Probab., Volume 21 (1993), pp. 248-289 | MR | Zbl

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

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

[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, Volume 129 (2004), pp. 182-218 | MR | Zbl

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

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

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

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

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

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

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

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

[16] J.F. Delmas 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] E. Derbez; G. Slade The scaling limit of lattice trees in high dimensions, Comm. Math. Phys., Volume 198 (1998), pp. 69-104 | MR | Zbl

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

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

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

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

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

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

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

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

[26] E.B. Dynkin; S.E. Kuznetsov ℕ-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] S.N. Evans; J.W. Pitman; A. Winter 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] S.N. Evans; A. Winter Subtree prune and re-graft: A reversible real tree valued Markov process (2005) (Preprint, arXiv:math.PR/05022266)

[29] P. Flajolet; A.M Odlyzko 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] J. Geiger; L. Kauffmann The shape of large Galton-Watson trees with possibly infinite variance, Random Structures Algorithms, Volume 25 (2004), pp. 311-335 | MR | Zbl

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

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

[33] B. Haas; G. Miermont 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] 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., Volume 41 (2000), pp. 1244-1293 | MR | Zbl

[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., Volume 20 (2003), pp. 413-485 | Numdam | MR | Zbl

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

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

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

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

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

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

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

[43] J.F. Le Gall 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] J.F. Le Gall The Brownian snake and solutions of Δu=u 2 in a domain, Probab. Th. Rel. Fields, Volume 102 (1995), pp. 393-432 | MR | Zbl

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

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

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

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

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

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

[51] J.F. Marckert; A. Mokkadem 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] J.F. Marckert; A. Mokkadem Limits of normalized quadrangulations. The Brownian map. Preprint (2004) (arXiv:math.PR/0403398)

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

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

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

[56] E.A. Perkins 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] 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., Volume 27 (1999), pp. 261-283 | MR | Zbl

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

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

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

Cité par Sources :