En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK

AUDIOVISUAL MATHEMATICS LIBRARY

AUDIOVISUAL MATHEMATICS LIBRARY

1

Condensation in random trees 1/3

Sélection

Cochez un dossier pour ajouter l'enregistrement à vos favoris. Décochez-le pour l'en enlever.

4

gerer mes paniers

Signaler une erreur
Multi angle
Auteurs : Kortchemski, Igor (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...
Résumé : We study a particular family of random trees which exhibit a condensation phenomenon (identified by Jonsson & Stefánsson in 2011), meaning that a unique vertex with macroscopic degree emerges. This falls into the more general framework of studying the geometric behavior of large random discrete structures as their size grows. Trees appear in many different areas such as computer science (where trees appear in the analysis of random algorithms for instance connected with data allocation), combinatorics (trees are combinatorial objects by essence), mathematical genetics (as phylogenetic trees), in statistical physics (for instance in connection with random maps as we will see below) and in probability theory (where trees describe the genealogical structure of branching processes, fragmentation processes, etc.). We shall specifically focus on Bienaymé–Galton–Watson trees (which is the simplest
possible genealogical model, where individuals reproduce in an asexual and stationary way), whose offspring distribution is subcritical and is regularly varying. The main tool is to code these trees by integer-valued random walks with negative drift, conditioned on a late return to the origin. The study of such random walks, which is of independent interest, reveals a "one-big jump principle" (identified by Armendáriz & Loulakis in 2011), thus explaining the condensation phenomenon.

Section 1 gives some history and motivations for studying Bienaymé–Galton–Watson trees.
Section 2 defines Bienaymé–Galton–Watson trees.
Section 3 explains how such trees can be coded by random walks, and introduce several useful tools, such as cyclic shifts and the Vervaat transformation, to study random walks under a conditioning involving positivity constraints.
Section 4 contains exercises to manipulate connections between BGW trees and random walks, and to study ladder times of downward skip-free random walks.
Section 5 gives estimates, such as maximal inequalities, for random walks in order to establish a "one-big jump principle".
Section 6 transfers results on random walks to random trees in order to identity the condensation phenomenon.

The goal of these lecture notes is to be as most self-contained as possible.

Keywords : ramdom trees; random walks; heavy tails; one-big jump principle

Codes MSC :
05C05 - Trees
 60G50 - Sums of independent random variables; random walks
 60J80 - Branching processes (Galton-Watson, birth-and-death, etc.)
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/2075/Abstracts/Abs_Kortchemski.pdf
Informations sur la Rencontre

Nom de la rencontre : Random Trees and Graphs Summer School / École d'été GRaphes et Arbres ALéatoires
Organisateurs de la rencontre : Albenque, Marie ; Bettinelli, Jérémie ; Ménard, Laurent ; Rué, Juanjo
Dates : 01/07/2019 - 05/07/2019
Année de la rencontre : 2019
URL Congrès : https://conferences.cirm-math.fr/2075.html

Données de citation

DOI : 10.24350/CIRM.V.19541003
Citer cette vidéo: Kortchemski, Igor (2019). Condensation in random trees 1/3. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19541003
URI : http://dx.doi.org/10.24350/CIRM.V.19541003

Voir aussi

Bibliographie

  • ABRAHAM, Romain, DELMAS, Jean-François, et al. Local limits of conditioned Galton-Watson trees: the condensation case. Electronic Journal of Probability, 2014, vol. 19. - http://emis.ams.org/journals/EJP-ECP/article/download/3164/3164-17754-1-PB.pdf

  • ADDARIO‐BERRY, Louigi. Tail bounds for the height and width of a random tree with a given degree sequence. Random Structures & Algorithms, 2012, vol. 41, no 2, p. 253-261. - https://doi.org/10.1002/rsa.20438

  • ADDARIO-BERRY, Louigi. A probabilistic approach to block sizes in random maps. arXiv preprint arXiv:1503.08159, 2015. - https://arxiv.org/abs/1503.08159

  • ALBENQUE, Marie, MARCKERT, Jean-François, et al. Some families of increasing planar maps. Electronic journal of probability, 2008, vol. 13, p. 1624-1671. - http://emis.ams.org/journals/EJP-ECP/article/download/563/563-1832-1-PB.pdf

  • ALDOUS, David. The continuum random tree. I. The Annals of Probability, 1991, p. 1-28. - https://www.jstor.org/stable/2244250

  • ALDOUS, David. The continuum random tree II: an overview. Stochastic analysis, 1991, vol. 167, p. 23-70. -

  • ALDOUS, David, et al. The continuum random tree III. The Annals of Probability, 1993, vol. 21, no 1, p. 248-289. - https://www.jstor.org/stable/2244761

  • ARMENDÁRIZ, Inés et LOULAKIS, Michail. Conditional distribution of heavy tailed random variables on large deviations of their sum. Stochastic Processes and their Applications, 2011, vol. 121, no 5, p. 1138-1147. - https://doi.org/10.1016/j.spa.2011.01.011

  • K. B. ATHREYA AND P. E. NEY, Branching processes, Springer-Verlag, New York, 1972. Die Grundlehren
    der mathematischen Wissenschaften, Band 196. -

  • BACAËR, Nicolas. A short history of mathematical population dynamics. Springer Science & Business Media, 2011. -

  • BENNIES, Jürgen et KERSTING, Götz. A random walk approach to Galton–Watson trees. Journal of Theoretical Probability, 2000, vol. 13, no 3, p. 777-803. - https://doi.org/10.1023/A:1007862612753

  • BERGER, Quentin. Notes on random walks in the Cauchy domain of attraction. Probability Theory and Related Fields, 2017, p. 1-44. - https://doi.org/10.1007/s00440-018-0887-0

  • BETTINELLI, Jérémie. Scaling limit of random planar quadrangulations with a boundary. In : Annales de l'IHP Probabilités et statistiques. 2015. p. 432-477. - https://doi.org/10.1214/13-AIHP581

  • BIENAYMÉ, Irénée-Jules. De la loi de multiplication et de la durée des familles. Soc. Philomat. Paris Extraits, Sér, 1845, vol. 5, no 37-39, p. 4. - http://www.cs.xu.edu/math/Sources/Bienayme/trans%201845.pdf

  • BINGHAM, Nicholas H., GOLDIE, Charles M., et TEUGELS, Jef L. Regular variation. Cambridge university press, 1989. -

  • BROUTIN, Nicolas et MARCKERT, Jean‐François. Asymptotics of trees with a prescribed degree sequence and applications. Random Structures & Algorithms, 2014, vol. 44, no 3, p. 290-316. - https://doi.org/10.1002/rsa.20463

  • CARACENI, Alessandra, et al. The scaling limit of random outerplanar maps. In : Annales de l'Institut Henri Poincaré, Probabilités et Statistiques. Institut Henri Poincaré, 2016. p. 1667-1686. - http://dx.doi.org/10.1214/15-AIHP694

  • CHEN, Xinxin, MIERMONT, Grégory, et al. Long Brownian bridges in hyperbolic spaces converge to Brownian trees. Electronic Journal of Probability, 2017, vol. 22. - http://dx.doi.org/10.1214/17-EJP68

  • CURIEN, Nicolas, HAAS, Bénédicte, et KORTCHEMSKI, Igor. The CRT is the scaling limit of random dissections. Random Structures & Algorithms, 2015, vol. 47, no 2, p. 304-327. - https://doi.org/10.1002/rsa.20554

  • CURIEN, Nicolas et KORTCHEMSKI, Igor. Random non‐crossing plane configurations: A conditioned Galton‐Watson tree approach. Random Structures & Algorithms, 2014, vol. 45, no 2, p. 236-260. - https://doi.org/10.1002/rsa.20481

  • CURIEN, Nicolas et KORTCHEMSKI, Igor. Percolation on random triangulations and stable looptrees. Probability Theory and Related Fields, 2015, vol. 163, no 1-2, p. 303-337. - http://dx.doi.org/10.1007/s00440-014-0593-5

  • DENISOV, Denis, DIEKER, Antonius Bernardus, SHNEER, Vsevolod, et al. Large deviations for random walks under subexponentiality: the big-jump domain. The Annals of Probability, 2008, vol. 36, no 5, p. 1946-1991. - http://dx.doi.org/10.1214/07-AOP382

  • DONEY, R. A. A large deviation local limit theorem. In : Mathematical Proceedings of the Cambridge Philosophical Society. Cambridge University Press, 1989. p. 575-577. - https://doi.org/10.1017/S030500410007794X

  • DRMOTA, Michael. Random trees: an interplay between combinatorics and probability. Springer Science & Business Media, 2009. -

  • DUQUESNE, Thomas, et al. A limit theorem for the contour process of condidtioned Galton--Watson trees. The Annals of Probability, 2003, vol. 31, no 2, p. 996-1027. - http://dx.doi.org/10.1214/aop/1048516543

  • DUQUESNE, Thomas et LE GALL, Jean-François. Random trees, Lévy processes and spatial branching processes. Société mathématique de France, 2002. -

  • DUQUESNE, Thomas et LE GALL, Jean-François. Probabilistic and fractal aspects of Lévy trees. Probability Theory and Related Fields, 2005, vol. 131, no 4, p. 553-603. - http://dx.doi.org/10.1007/s00440-004-0385-4

  • EVANS, Steven N., PITMAN, Jim, et WINTER, Anita. Rayleigh processes, real trees, and root growth with re-grafting. Probability Theory and Related Fields, 2006, vol. 134, no 1, p. 81-126. - http://dx.doi.org/10.1007/s00440-004-0411-6

  • FELLER, Willliam. An introduction to probability theory and its applications Vol II John Wiley & Sons, 2071. -

  • FÉRAY, Valentin et KORTCHEMSKI, Igor. The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees. arXiv preprint arXiv:1712.06542, 2017. - https://arxiv.org/abs/1712.06542

  • FUK, D. Kh et NAGAEV, Sergey V. Probability inequalities for sums of independent random variables. Theory of Probability & Its Applications, 1971, vol. 16, no 4, p. 643-660. - https://doi.org/10.1137/1116071

  • GEIGER, Jochen et KERSTING, Götz. The Galton-Watson tree conditioned on its height. Probability Theory and Mathematical Statistics (Vilnius, 1998), 1999, p. 277-286. - https://www.uni-frankfurt.de/65701929/conheight.pdf

  • GROMOV, Michael. Groups of polynomial growth and expanding maps (with an appendix by Jacques Tits). Publications Mathématiques de l'IHÉS, 1981, vol. 53, p. 53-78. - http://www.numdam.org/item?id=PMIHES_1981__53__53_0

  • HAAS, Bénédicte, MIERMONT, Grégory, et al. Scaling limits of Markov branching trees with applications to Galton–Watson and random unordered trees. The Annals of Probability, 2012, vol. 40, no 6, p. 2589-2666. - http://dx.doi.org/10.1214/11-AOP686

  • HARRIS, Theodore Edward. First passage and recurrence distributions. RAND CORP SANTA MONICA CA, 1951. - https://apps.dtic.mil/dtic/tr/fulltext/u2/603915.pdf

  • HEYDE, Chris C. et SENETA, Eugene. 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 IJ Bienaymé. Biometrika, 1972, vol. 59, no 3, p. 680-683. - https://doi.org/10.1093/biomet/59.3.680

  • JANSON, Svante, et al. Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation. Probability Surveys, 2012, vol. 9, p. 103-252. - http://dx.doi.org/10.1214/11-PS188

  • JANSON, Svante, STEFÁNSSON, Sigurdur Örn, et al. Scaling limits of random planar maps with a unique large face. The Annals of Probability, 2015, vol. 43, no 3, p. 1045-1081. - http://dx.doi.org/10.1214/13-AOP871

  • JANSON, Svante, STEFÁNSSON, Sigurdur Örn, et al. Scaling limits of random planar maps with a unique large face. The Annals of Probability, 2015, vol. 43, no 3, p. 1045-1081. - http://dx.doi.org/10.1214/13-AOP871

  • JONSSON, Thordur et STEFÁNSSON, Sigurdur Örn. Condensation in nongeneric trees. Journal of Statistical Physics, 2011, vol. 142, no 2, p. 277-313. - http://dx.doi.org/10.1007/s10955-010-0104-8

  • KENDALL, David G. The genealogy of genealogy branching processes before (and after) 1873. Bulletin of the London Mathematical Society, 1975, vol. 7, no 3, p. 225-253. - https://doi.org/10.1112/blms/7.3.225

  • KENNEDY, Douglas P. The Galton-Watson process conditioned on the total progeny. Journal of Applied Probability, 1975, vol. 12, no 4, p. 800-806. - https://doi.org/10.2307/3212730

  • KESTEN, Harry. Subdiffusive behavior of random walk on a random cluster. In : Annales de l'IHP Probabilités et statistiques. 1986. p. 425-487. - http://www.numdam.org/item?id=AIHPB_1986__22_4_425_0

  • KORTCHEMSKI, Igor. Invariance principles for Galton–Watson trees conditioned on the number of leaves. Stochastic Processes and Their Applications, 2012, vol. 122, no 9, p. 3126-3172. - https://doi.org/10.1016/j.spa.2012.05.013

  • KORTCHEMSKI, Igor. Limit theorems for conditioned non-generic Galton–Watson trees. In : Annales de l'IHP Probabilités et statistiques. 2015. p. 489-511. - https://doi.org/10.1214/13-AIHP580

  • KORTCHEMSKI, Igor, RICHIER, Loïc, et al. Condensation in critical Cauchy Bienaymé–Galton–Watson trees. The Annals of Applied Probability, 2019, vol. 29, no 3, p. 1837-1877. - http://dx.doi.org/10.1214/18-AAP1447

  • KRIKUN, Maxim A. Uniform infinite planar triangulation and related time-reversed critical branching process. Journal of Mathematical Sciences, 2005, vol. 131, no 2, p. 5520-5537. - http://dx.doi.org/10.1007/s10958-005-0424-4

  • GALL, Jean-François Le. Random geometry on the sphere. arXiv preprint arXiv:1403.7943, 2014. - https://arxiv.org/abs/1403.7943

  • LE GALL, Jean-François, et al. Random trees and applications. Probability surveys, 2005, vol. 2, p. 245-311. - http://dx.doi.org/10.1214/154957805100000140

  • LE GALL, Jean-François. Itô's excursion theory and random trees. Stochastic Processes and Their Applications, 2010, vol. 120, no 5, p. 721-749. - https://doi.org/10.1016/j.spa.2010.01.015

  • LE GALL, Jean-Francois, LE JAN, Yves, et al. Branching processes in Lévy processes: the exploration process. The Annals of Probability, 1998, vol. 26, no 1, p. 213-252. - http://dx.doi.org/10.1214/aop/1022855417

  • LYONS, Russell, PEMANTLE, Robin, et PERES, Yuval. Conceptual proofs of L log L criteria for mean behavior of branching processes. The Annals of Probability, 1995, p. 1125-1138. - https://www.jstor.org/stable/2244865

  • LYONS, Russell et PERES, Yuval. Probability on trees and networks. Cambridge University Press, 2017. -

  • MILLER, Jason et SHEFFIELD, Scott. An axiomatic characterization of the Brownian map. arXiv preprint arXiv:1506.03806, 2015. - https://arxiv.org/abs/1506.03806

  • NAGAEV, Sergey Victorovich. On the asymptotic behaviour of one-sided large deviation probabilities. Teoriya Veroyatnostei i ee Primeneniya, 1981, vol. 26, no 2, p. 369-372. - http://dx.doi.org/10.1137/1126035%7D

  • PANAGIOTOU, Konstantinos et STUFLER, Benedikt. Scaling limits of random Pólya trees. Probability Theory and Related Fields, 2018, vol. 170, no 3-4, p. 801-820.https://arxiv.org/abs/1808.08140 - http://dx.doi.org/10.1007/s00440-017-0770-4

  • WELLER, Kerstin, STUFLER, Benedikt, et PANAGIOTOU, Konstantinos. Scaling Limits of Random Graphs from Subcritical Classes. Discrete Mathematics & Theoretical Computer Science, 2015. - https://arxiv.org/abs/1411.1865

  • PAULIN, Frédéric. The Gromov topology on R-trees. Topology and its Applications, 1989, vol. 32, no 3, p. 197-221. - https://doi.org/10.1016/0166-8641(89)90029-1

  • PITMAN, Jim et RIZZOLO, Douglas. Schröder's problems and scaling limits of random trees. Transactions of the American Mathematical Society, 2015, vol. 367, no 10, p. 6943-6969. - http://dx.doi.org/10.1090/S0002-9947-2015-06254-0

  • RAMZEWS, Leon et STUFLER, Benedikt. Simply Generated Unrooted Plane Trees. arXiv preprint arXiv:1808.08140, 2018. - https://arxiv.org/abs/1808.08140

  • RICHIER, Loïc. Limits of the boundary of random planar maps. Probability Theory and Related Fields, 2018, vol. 172, no 3-4, p. 789-827. - http://dx.doi.org/10.1007/s00440-017-0820-y

  • 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. In : Annales de l'IHP Probabilités et statistiques. 2015. p. 512-532. - https://doi.org/10.1214/13-AIHP594

  • STEFÁNSSON, Sigurdur Örn et STUFLER, Benedikt. Geometry of large Boltzmann outerplanar maps. Random Structures & Algorithms, 2017. - https://doi.org/10.1002/rsa.20834

  • STEFFENSEN, Johan Frederik. Om sandsynligheden for at afkommet uddør. Matematisk tidsskrift. B, 1930, p. 19-23. - https://www.jstor.org/stable/24529732

  • STUFLER, Benedikt. Limits of random tree-like discrete structures. arXiv preprint arXiv:1612.02580, 2016. - https://arxiv.org/abs/1612.02580

  • STUFLER, Benedikt, et al. Scaling limits of random outerplanar maps with independent link-weights. In : Annales de l'Institut Henri Poincaré, Probabilités et Statistiques. Institut Henri Poincaré, 2017. p. 900-915. - http://dx.doi.org/10.1214/16-AIHP741

  • WATSON, Henry William et GALTON, Francis. On the probability of the extinction of families. The Journal of the Anthropological Institute of Great Britain and Ireland, 1875, vol. 4, p. 138-144. - http://dx.doi.org/10.2307/2841222


Sélection

Cochez un dossier pour ajouter l'enregistrement à vos favoris. Décochez-le pour l'en enlever.

4

gerer mes paniers

Signaler une erreur