Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 2 (2005) open journal systems 

Random trees and applications

Jean-François Le Gall, ENS Paris

We discuss several connections between discrete and continuous random trees. In the discrete setting, we focus on Galton-Watson trees under various conditionings. In particular, we present a simple approach to Aldous' theorem giving the convergence in distribution of the contour process of conditioned Galton-Watson trees towards the normalized Brownian excursion. We also briefly discuss applications to combinatorial trees. In the continuous setting, we use the formalism of real trees, which yields an elegant formulation of the convergence of rescaled discrete trees towards continuous objects. We explain the coding of real trees by functions, which is a continuous version of the well-known coding of discrete trees by Dyck paths. We pay special attention to random real trees coded by Brownian excursions, and in a particular we provide a simple derivation of the marginal distributions of the CRT. The last section is an introduction to the theory of the Brownian snake, which combines the genealogical structure of random real trees with independent spatial motions. We introduce exit measures for the Brownian snake and we present some applications to a class of semilinear partial differential equations.

AMS 2000 subject classifications: Primary 60J80; secondary 05C05, 35J65, 60C05, 60J65.

Keywords: random tree, contour process, conditioned tree, Brownian motion, Brownian excursion, real tree, coding of trees, CRT, Brownian snake, exit measure, partial differential equation.

Creative Common LOGO

Full Text: PDF

Gall, Jean-François Le, Random trees and applications, Probability Surveys, 2, (2005), 245-311 (electronic).


[1]   D. Aldous. The continuum random tree I. Ann. Probab. 19 (1991), 1-28. MR1085326

[2]   D. Aldous. The continuum random tree III. Ann. Probab. 21 (1993), 248-289. MR1207226

[3]   D. Aldous. Tree-based models for random distribution of mass. J. Stat. Phys. 73 (1993), 625-641. MR1251658

[4]   R.M. Blumenthal. Excursions of Markov Processes. Birkhäuser 1992.

[5]   M. Bramson, J.T. Cox, J.F. Le Gall. Super-Brownian limits of voter model clusters. Ann. Probab. 29 (2001), 1001-1032. MR1872733

[6]   P. Chassaing, G. Schaeffer. Random planar lattices and integrated superBrownian excursion. Probab. Th. Rel. Fields 128 (2004), 161-212. MR2031225

[7]   E. Derbez, G. Slade. The scaling limit of lattice trees in high dimensions. Comm. Math. Phys. 198 (1998), 69-104. MR1620301

[8]   J.S. Dhersin, J.F. Le Gall. Wiener’s test for super-Brownian motion and for the Brownian snake. Probab. Th. Rel. Fields 108 (1997), 103-129. MR1452552

[9]   M. Drmota, B. Gittenberger. On the profile of random trees. Random Struct. Alg. 10 (1997), 421-451. MR1608230

[10]   T. Duquesne. A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab. 31 (2003), 996–1027. MR1964956

[11]   T. Duquesne, J.F. Le Gall. Random Trees, Lévy Processes and Spatial Branching Processes. Astérisque 281 (2002)

[12]   T. Duquesne, J.F. Le Gall. Probabilistic and fractal aspects of Lévy trees. Probab. Th. Rel. Fields 131 (2005), 553-603. MR2147221

[13]   E.B. Dynkin. A probabilistic approach to one class of nonlinear differential equations. Probab. Th. Rel. Fields 90 (1991), 89-115. MR1109476

[14]   E.B. Dynkin. Diffusions, Superdiffusions and Partial Differential Equations. American Math. Society 2002. MR1883198

[15]   E.B. Dynkin. Superdiffusions and Positive Solutions of Nonlinear Partial Differential Equations. American Math. Society 2004. MR2089791

[16]   S.N. Ethier, T. Kurtz. Markov Processes, Characterization and Convergence. Wiley 1986.

[17]   S.N. Evans, J. Pitman, A. Winter. Rayleigh processes, real trees, and root growth with re-grafting. Probab. Th. Rel. Fields, to appear.

[18]   S.N. Evans, A. Winter. Subtree prune and re-graft: A reversible tree-valued Markov process. Ann. Probab., to appear. MR1159560

[19]   M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Birkhäuser 1999.

[20]   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. MR2041829

[21]   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. MR1757958

[22]   R. van der Hofstad, A. Sakai. Gaussian scaling for the critical spread-out contact process above the upper critical dimension. Electron. J. Probab. 9 (2004), 710-769. MR2110017

[23]   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. 39 (2003), 413-485. MR1978987

[24]   W.D. Kaigh. An invariance principle for random walk conditioned by a late return to zero. Ann. Probab. 4 (1976), 115-121. MR415706

[25]   J.F. Le Gall. Brownian excursions, trees and measure-valued processes. Ann. Probab. 19 (1991), 1399-1439. MR1127710

[26]   J.F. Le Gall. The uniform random tree in a Brownian excursion. Probab. Theory Rel. Fields 95 (1993), 25-46. MR1207305

[27]   J.F. Le Gall. Spatial Branching Processes, Random Snakes and Partial Differential Equations. Birkhäuser 1999.

[28]   J.F. Le Gall. Random trees and spatial branching processes. Maphysto Lecture Notes Series (University of Aarhus), vol. 9 (80 pp.), 2000. Available at   http://www.maphysto.dk/publications/MPS-LN/2000/9.pdf

[29]   J.F. Le Gall, Y. Le Jan. Branching processes in Lévy processes: The exploration process. Ann. Probab. 26 (1998), 213-252. MR1617047

[30]   J.F. Le Gall, M. Weill. Conditioned Brownian trees. Ann. Inst. H. Poincaré Probab. Statist., to appear.

[31]   J.F. Marckert, A. Mokkadem. The depth first processes of Galton-Watson trees converge to the same Brownian excursion. Ann. Probab. 31 (2003), 1655-1678. MR1989446

[32]   J.-F. Marckert, G. Miermont. Invariance principles for labeled mobiles and bipartite planar maps. Preprint (2005).

[33]   B. Mselati. Classification and probabilistic representation of the positive solutions of a semilinear elliptic equation. Memoirs Amer. Math. Soc. 798 (2004)

[34]   J. Neveu. Arbres et processus de Galton-Watson. Ann. Inst. Henri Poincaré Probab. Stat. 22 (1986), 199-207. MR850756

[35]   E.A. Perkins. Dawson-Watanabe superprocesses and measure-valued diffusions. Ecole d’été de probabilités de Saint-Flour 1999. In: Lecture Notes Math. 1781. Springer, 2002. MR1915445

[36]   J.W. Pitman. Combinatorial stochastic processes. Ecole d’été de probabilités de Saint-Flour 2002. Lecture Notes Math., Springer. To appear.

[37]   S.C. Port, C.J. Stone. Brownian Motion and Classical Potential Theory. Academic, New York, 1978. MR492329

[38]   D. Revuz, M. Yor. Continuous Martingales and Brownian Motion. Springer 1991.

[39]   L.C.G. Rogers, D. Williams. Diffusions, Markov Processes and Martingales. Vol.2: Itô Calculus. Wiley 1987. MR921238

[40]   F. Spitzer. Principles of Random Walk. Van Nostrand 1963.

[41]   R.P. Stanley. Enumerative Combinatorics, Vol.2. Cambridge University Press 1999

Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787