Arbres et marches aléatoires

Kortchemski, Igor

doi:10.5802/xups.2016-01

Kortchemski, Igor ¹

¹ CNRS & CMAP, École polytechnique, Université Paris-Saclay

Journées mathématiques X-UPS, Arbres et marches aléatoires (2016), pp. 1-57.

Résumé

Nous nous intéressons à de grands arbres aléatoires qui décrivent la généalogie d’une population se reproduisant de manière asexuée. Ce modèle a été introduit à la fin du xix^e siècle par Bienaymé et Galton & Watson pour prédire l’extinction des noms nobles en Angleterre. En n’utilisant essentiellement que des outils au programme des classes préparatoires scientifiques, nous étudions la géométrie de ces arbres en les codant par des marches aléatoires conditionnées, que nous analysons à leur tour en utilisant des arguments combinatoires et analytiques.

Publié le : 2024-08-06

DOI : 10.5802/xups.2016-01

Affiliations des auteurs :

Kortchemski, Igor ¹

¹ CNRS & CMAP, École polytechnique, Université Paris-Saclay

@incollection{XUPS_2016____1_0,
     author = {Kortchemski, Igor},
     title = {Arbres et marches al\'eatoires},
     booktitle = {Arbres et marches al\'eatoires},
     series = {Journ\'ees math\'ematiques X-UPS},
     pages = {1--57},
     publisher = {Les \'Editions de l{\textquoteright}\'Ecole polytechnique},
     year = {2016},
     doi = {10.5802/xups.2016-01},
     language = {fr},
     url = {http://archive.numdam.org/articles/10.5802/xups.2016-01/}
}

TY  - JOUR
AU  - Kortchemski, Igor
TI  - Arbres et marches aléatoires
JO  - Journées mathématiques X-UPS
PY  - 2016
SP  - 1
EP  - 57
PB  - Les Éditions de l’École polytechnique
UR  - http://archive.numdam.org/articles/10.5802/xups.2016-01/
DO  - 10.5802/xups.2016-01
LA  - fr
ID  - XUPS_2016____1_0
ER  -

%0 Journal Article
%A Kortchemski, Igor
%T Arbres et marches aléatoires
%J Journées mathématiques X-UPS
%D 2016
%P 1-57
%I Les Éditions de l’École polytechnique
%U http://archive.numdam.org/articles/10.5802/xups.2016-01/
%R 10.5802/xups.2016-01
%G fr
%F XUPS_2016____1_0

Kortchemski, Igor. Arbres et marches aléatoires. Journées mathématiques X-UPS, Arbres et marches aléatoires (2016), pp. 1-57. doi : 10.5802/xups.2016-01. http://archive.numdam.org/articles/10.5802/xups.2016-01/

Bibliographie
Cité par

[AB12] Addario-Berry, Louigi Tail bounds for the height and width of a random tree with a given degree sequence, Random Structures Algorithms, Volume 41 (2012) no. 2, pp. 253-261 | DOI | MR | Zbl

[AB19] Addario-Berry, Louigi A probabilistic approach to block sizes in random maps, ALEA Lat. Am. J. Probab. Math. Stat., Volume 16 (2019) no. 1, pp. 1-13 | DOI | MR | Zbl

[AD14a] Abraham, Romain; Delmas, Jean-François Local limits of conditioned Galton-Watson trees : the infinite spine case, Electron. J. Probab., Volume 19 (2014), 2, 19 pages | DOI | MR | Zbl

[AD14b] Abraham, Romain; Delmas, Jean-François Local limits of conditioned Galton-Watson trees : the condensation case, Electron. J. Probab., Volume 19 (2014), 56, 29 pages | DOI | MR | Zbl

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

[Ald91b] Aldous, David 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 | DOI | MR | Zbl

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

[AM08] Albenque, Marie; Marckert, Jean-François Some families of increasing planar maps, Electron. J. Probab., Volume 13 (2008), 56 | DOI | MR | Zbl

[AN72] Athreya, Krishna B.; Ney, Peter E. Branching processes, Grundlehren Math. Wissen., 196, Springer-Verlag, New York, 1972 | DOI | MR

[Bac11] Bacaër, Nicolas A short history of mathematical population dynamics, Springer-Verlag London, Ltd., London, 2011 | DOI | MR

[Bet15] Bettinelli, Jérémie Scaling limit of random planar quadrangulations with a boundary, Ann. Inst. Henri Poincaré Probab. Stat., Volume 51 (2015) no. 2, pp. 432-477 | DOI | Numdam | MR | Zbl

[BFSS01] Banderier, Cyril; Flajolet, Philippe; Schaeffer, Gilles; Soria, Michèle Random maps, coalescing saddles, singularity analysis, and Airy phenomena, Random Structures Algorithms, Volume 19 (2001) no. 3-4, pp. 194-246 | DOI | MR | Zbl

[Bie45] Bienaymé, Jules De la loi de multiplication et de la durée des familles : probabilités, Société philomathique de Paris (1845)

[BK00] Bennies, Jürgen; Kersting, Götz A random walk approach to Galton-Watson trees, J. Theoret. Probab., Volume 13 (2000) no. 3, pp. 777-803 | DOI | MR | Zbl

[BM14] Broutin, Nicolas; Marckert, Jean-François Asymptotics of trees with a prescribed degree sequence and applications, Random Structures Algorithms, Volume 44 (2014) no. 3, pp. 290-316 | DOI | MR | Zbl

[Car16] Caraceni, Alessandra The scaling limit of random outerplanar maps, Ann. Inst. H. Poincaré Probab. Statist., Volume 52 (2016) no. 4, pp. 1667-1686 | DOI | MR | Zbl

[CHK15a] Curien, Nicolas; Haas, Bénédicte; Kortchemski, Igor The CRT is the scaling limit of random dissections, Random Structures Algorithms, Volume 47 (2015) no. 2, pp. 304-327 | DOI | MR | Zbl

[CHK15b] Curien, Nicolas; Haas, Bénédicte; Kortchemski, Igor The CRT is the scaling limit of random dissections, Random Structures Algorithms, Volume 47 (2015) no. 2, pp. 304-327 | DOI | MR | Zbl

[CK14a] Curien, Nicolas; Kortchemski, Igor Random non-crossing plane configurations : a conditioned Galton-Watson tree approach, Random Structures Algorithms, Volume 45 (2014) no. 2, pp. 236-260 | DOI | MR | Zbl

[CK14b] Curien, Nicolas; Kortchemski, Igor Random stable looptrees, Electron. J. Probab., Volume 19 (2014), 108, 35 pages | DOI | MR | Zbl

[CK15] Curien, Nicolas; Kortchemski, Igor Percolation on random triangulations and stable looptrees, Probab. Theory Related Fields, Volume 163 (2015) no. 1-2, pp. 303-337 | DOI | MR | Zbl

[Dev12] Devroye, Luc Simulating size-constrained Galton-Watson trees, SIAM J. Comput., Volume 41 (2012) no. 1, pp. 1-11 | DOI | MR | Zbl

[DLG02] Duquesne, Thomas; Le Gall, Jean-François Random trees, Lévy processes and spatial branching processes, Astérisque, 281, Société Mathématique de France, Paris, 2002 | Numdam | MR

[DLG05] Duquesne, Thomas; Le Gall, Jean-François Probabilistic and fractal aspects of Lévy trees, Probab. Theory Related Fields, Volume 131 (2005) no. 4, pp. 553-603 | DOI | MR | Zbl

[Drm09] Drmota, Michael Random trees, Springer Wien, NewYork, Vienna, 2009 | DOI | MR

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

[DZ86] Dershowitz, Nachum; Zaks, Shmuel Ordered trees and noncrossing partitions, Discrete Math., Volume 62 (1986) no. 2, pp. 215-218 | DOI | MR | Zbl

[EPW06] Evans, Steven N.; Pitman, Jim; Winter, Anita Rayleigh processes, real trees, and root growth with re-grafting, Probab. Theory Related Fields, Volume 134 (2006) no. 1, pp. 81-126 | DOI | MR | Zbl

[GK99] Geiger, J.; Kersting, G. The Galton-Watson tree conditioned on its height, Probability theory and mathematical statistics. Proc. 7th intern. Vilnius conference (Vilnius, August 1998, TEV, Vilnius ; VSP, Utrecht, 1999, pp. 277-286 | Zbl

[Gou08] Gourdon, Xavier Les maths en tête : Analyse, Ellipses Marketing, Paris, 2008

[Gro81] Gromov, Mikhael Groups of polynomial growth and expanding maps, Publ. Math. Inst. Hautes Études Sci. (1981) no. 53, pp. 53-73 | DOI | Numdam | MR | Zbl

[Har52] Harris, T. E. First passage and recurrence distributions, Trans. Amer. Math. Soc., Volume 73 (1952), pp. 471-486 | DOI | MR | Zbl

[HM12] Haas, Bénédicte; Miermont, Grégory Scaling limits of Markov branching trees, with applications to Galton-Watson and random unordered trees, Ann. Probab., Volume 40 (2012), pp. 2589-2666 | MR | Zbl

[HS72] Heyde, C. C.; Seneta, E. Studies in the history of probability and statistics. XXXI. The simple branching process, a turning point test and a fundamental inequality : a historical note on I. J. Bienaymé, Biometrika, Volume 59 (1972), pp. 680-683 | MR

[Jan12] Janson, Svante Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probab. Surv., Volume 9 (2012), pp. 103-252 | DOI | MR | Zbl

[JS11] Jonsson, Thordur; Stefánsson, Sigurdur Örn Condensation in nongeneric trees, J. Stat. Phys., Volume 142 (2011) no. 2, pp. 277-313 | DOI | MR | Zbl

[JS15] Janson, Svante; Stefánsson, Sigurdur Örn Scaling limits of random planar maps with a unique large face, Ann. Probab., Volume 43 (2015) no. 3, pp. 1045-1081 | DOI | MR | Zbl

[Ken75a] Kendall, David G. The genealogy of genealogy : branching processes before (and after) 1873, Bull. London Math. Soc., Volume 7 (1975) no. 3, pp. 225-253 (avec un appendice en français contenant l’article de 1845 de Bienaymé) | DOI | MR | Zbl

[Ken75b] Kennedy, Douglas P. The Galton-Watson process conditioned on the total progeny, J. Appl. Probability, Volume 12 (1975) no. 4, pp. 800-806 | DOI | MR | Zbl

[Kes86] Kesten, Harry Subdiffusive behavior of random walk on a random cluster, Ann. Inst. H. Poincaré Probab. Statist., Volume 22 (1986) no. 4, pp. 425-487 | Numdam | MR | Zbl

[KM16] Kortchemski, Igor; Marzouk, Cyril Triangulating stable laminations, Electron. J. Probab., Volume 21 (2016), 11, 31 pages | DOI | MR | Zbl

[KM17] Kortchemski, Igor; Marzouk, Cyril Simply generated non-crossing partitions, Combin. Probab. Comput., Volume 26 (2017) no. 4, pp. 560-592 | DOI | MR | Zbl

[Kol86] Kolchin, Valentin F. Random mappings, Translation Series in Math. and Engineering, Optimization Software, Inc., New York, 1986 | MR

[Kor12] Kortchemski, Igor Invariance principles for Galton-Watson trees conditioned on the number of leaves, Stochastic Process. Appl., Volume 122 (2012) no. 9, pp. 3126-3172 | DOI | MR | Zbl

[Kor14] Kortchemski, Igor Random stable laminations of the disk, Ann. Probab., Volume 42 (2014) no. 2, pp. 725-759 | MR | Zbl

[Kor15] Kortchemski, Igor Limit theorems for conditioned non-generic Galton-Watson trees, Ann. Inst. Henri Poincaré Probab. Stat., Volume 51 (2015) no. 2, pp. 489-511 | DOI | Numdam | MR | Zbl

[Kre72] Kreweras, G. Sur les partitions non croisées d’un cycle, Discrete Math., Volume 1 (1972) no. 4, pp. 333-350 | DOI | MR | Zbl

[Kri05] Krikun, M. A. Uniform infinite planar triangulation and related time-reversed critical branching process, J. Math. Sci., Volume 131 (2005) no. 2, pp. 5520-5537 | DOI

[LG10] Le Gall, Jean-François Itô’s excursion theory and random trees, Stochastic Process. Appl., Volume 120 (2010) no. 5, pp. 721-749 | DOI | MR | Zbl

[LG14] Le Gall, Jean-François Random geometry on the sphere, Proceedings of the ICM 2014, Kyung Moon Sa, Seoul, 2014, pp. 421-442 (http://www.icm2014.org/download/Proceedings_Volume_I.pdf) | Zbl

[LGLJ98] Le Gall, Jean-Francois; Le Jan, Yves Branching processes in Lévy processes : the exploration process, Ann. Probab., Volume 26 (1998) no. 1, pp. 213-252 | DOI | MR | Zbl

[LP16] Lyons, Russell; Peres, Yuval Probability on trees and networks, Cambridge Series in Statistical and Probabilistic Math., 42, Cambridge University Press, New York, 2016 | DOI

[McC06] McCammond, Jon Noncrossing partitions in surprising locations, Amer. Math. Monthly, Volume 113 (2006) no. 7, pp. 598-610 | DOI | MR | Zbl

[MM78] Meir, A.; Moon, J. W. On the altitude of nodes in random trees, Canad. J. Math., Volume 30 (1978) no. 5, pp. 997-1015 | DOI | MR | Zbl

[MP02] Marckert, Jean-François; Panholzer, Alois Noncrossing trees are almost conditioned Galton-Watson trees, Random Structures Algorithms, Volume 20 (2002) no. 1, pp. 115-125 | DOI | MR | Zbl

[MS21] Miller, Jason; Sheffield, Scott An axiomatic characterization of the Brownian map, J. Éc. polytech. Math., Volume 8 (2021), pp. 609-731 | DOI | Numdam | MR | Zbl

[Nev86] Neveu, J. Arbres et processus de Galton-Watson, Ann. Inst. H. Poincaré Probab. Statist., Volume 22 (1986) no. 2, pp. 199-207 | Numdam | MR | Zbl

[Pau89] Paulin, Frédéric The Gromov topology on $R$ -trees, Topology Appl., Volume 32 (1989) no. 3, pp. 197-221 | DOI | MR | Zbl

[PS18] Panagiotou, Konstantinos; Stufler, Benedikt Scaling limits of random Pólya trees, Probab. Theory Related Fields, Volume 170 (2018) no. 3-4, pp. 801-820 | DOI | MR | Zbl

[PSW16] Panagiotou, Konstantinos; Stufler, Benedikt; Weller, Kristin Scaling limits of random graphs from subcritical classes, Ann. Probab., Volume 44 (2016) no. 5, pp. 3291-3334 | DOI | MR | Zbl

[Riz15] Rizzolo, Douglas 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., Volume 51 (2015) no. 2, pp. 512-532 | DOI | Numdam | MR | Zbl

[Spi76] Spitzer, Frank Principles of random walk, Graduate Texts in Math., 34, Springer-Verlag, New York-Heidelberg, 1976 | DOI | MR

[Ste30] Steffensen, J. F. Om Sandsynligheden for at Afkommet uddør, Matematisk tidsskrift. B (1930), pp. 19-23 http://www.jstor.org/stable/24529732 | Zbl

[WG75] Watson, H. W.; Galton, Francis On the probability of the extinction of families, The Journal of the Anthropological Institute of Great Britain and Ireland, Volume 4 (1875), pp. 138-144 http://www.jstor.org/stable/2841222 | DOI

Cité par Sources :