Arbres et marches aléatoires

Igor Kortchemski

doi:10.5802/xups.2016-01

Igor Kortchemski ¹

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

Journées mathématiques X-UPS (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 :

Igor Kortchemski ¹

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

@incollection{XUPS_2016____1_0,
     author = {Igor Kortchemski},
     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 = {https://proceedings.centre-mersenne.org/articles/10.5802/xups.2016-01/}
}

TY  - JOUR
AU  - Igor Kortchemski
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  - https://proceedings.centre-mersenne.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 Igor Kortchemski
%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 https://proceedings.centre-mersenne.org/articles/10.5802/xups.2016-01/
%R 10.5802/xups.2016-01
%G fr
%F XUPS_2016____1_0

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

Bibliographie
Cité par

[AB12] Louigi Addario-Berry 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] Louigi Addario-Berry 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] Romain Abraham; Jean-François Delmas Local limits of conditioned Galton-Watson trees : the infinite spine case, Electron. J. Probab., Volume 19 (2014), 2, 19 pages | DOI | MR | Zbl

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

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

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

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

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

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

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

[Bet15] Jérémie Bettinelli 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] Cyril Banderier; Philippe Flajolet; Gilles Schaeffer; Michèle Soria 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] Jules Bienaymé De la loi de multiplication et de la durée des familles : probabilités, Société philomathique de Paris (1845)

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

[BM14] Nicolas Broutin; Jean-François Marckert 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] Alessandra Caraceni 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] Nicolas Curien; Bénédicte Haas; Igor Kortchemski The CRT is the scaling limit of random dissections, Random Structures Algorithms, Volume 47 (2015) no. 2, pp. 304-327 | DOI | MR | Zbl

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

[CK14a] Nicolas Curien; Igor Kortchemski 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] Nicolas Curien; Igor Kortchemski Random stable looptrees, Electron. J. Probab., Volume 19 (2014), 108, 35 pages | DOI | MR | Zbl

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

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

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

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

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

[Duq03] Thomas Duquesne 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] Nachum Dershowitz; Shmuel Zaks Ordered trees and noncrossing partitions, Discrete Math., Volume 62 (1986) no. 2, pp. 215-218 | DOI | MR | Zbl

[EPW06] Steven N. Evans; Jim Pitman; Anita Winter 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] J. Geiger; G. Kersting 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] Xavier Gourdon Les maths en tête : Analyse, Ellipses Marketing, Paris, 2008

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

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

[HM12] Bénédicte Haas; Grégory Miermont 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] C. C. Heyde; E. Seneta 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] Svante Janson Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probab. Surv., Volume 9 (2012), pp. 103-252 | DOI | MR | Zbl

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

[JS15] Svante Janson; Sigurdur Örn Stefánsson 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] David G. Kendall 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] Douglas P. Kennedy The Galton-Watson process conditioned on the total progeny, J. Appl. Probability, Volume 12 (1975) no. 4, pp. 800-806 | DOI | MR | Zbl

[Kes86] Harry Kesten 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] Igor Kortchemski; Cyril Marzouk Triangulating stable laminations, Electron. J. Probab., Volume 21 (2016), 11, 31 pages | DOI | MR | Zbl

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

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

[Kor12] Igor Kortchemski 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] Igor Kortchemski Random stable laminations of the disk, Ann. Probab., Volume 42 (2014) no. 2, pp. 725-759 | MR | Zbl

[Kor15] Igor Kortchemski 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] G. Kreweras Sur les partitions non croisées d’un cycle, Discrete Math., Volume 1 (1972) no. 4, pp. 333-350 | DOI | MR | Zbl

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

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

[LG14] Jean-François Le Gall 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] Jean-Francois Le Gall; Yves Le Jan Branching processes in Lévy processes : the exploration process, Ann. Probab., Volume 26 (1998) no. 1, pp. 213-252 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

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

[Riz15] Douglas Rizzolo 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] Frank Spitzer Principles of random walk, Graduate Texts in Math., 34, Springer-Verlag, New York-Heidelberg, 1976 | DOI | MR

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

[WG75] H. W. Watson; Francis Galton 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 :