Instructor : Igor Kortchemski

Consider a population that undergoes asexual and homogeneous reproduction over time, originating from a single individual and eventually ceasing to exist after producing a total of n individuals. What is the order of magnitude of the maximum number of children of an individual in this population when n tends to infinity? This question is equivalent to studying the largest degree of a large Bienaymé-Galton-Watson random tree. We identify a regime where a condensation phenomenon occurs, in which the second greatest degree is negligible compared to the greatest degree. The use of the "one-big jump principle" of certain random walks is a key tool for studying this phenomenon. Finally, we discuss applications of these results to other combinatorial models.

Outline:

Introduction (limits of random trees)
I. Bienaymé trees and random walks

1) Coding trees
2) Connection with conditioned random walks [end of day 1]
3) The Vervaat transform

II. A one-big-jump principle

1) A local estimate
2) One-big-jump principle [end of day 2]
3) An application

III. Condensation phenomena in random trees

1) Largest degrees
2) Structure of the tree
3) Height of the condensation vertex [end of day 3]

Course material

Lecture notes:

Literature

I. Armendáriz, M. Loulakis, Conditional distribution of heavy tailed random variables on large deviations of their sum. Stochastic processes and their applications, 121(5), 1138-1147 (2011).
A. Dembo and O. Zeitouni. Large deviations techniques and applications. Vol. 38. Springer Science & Business Media (2009).
D. Denisov, A. B. Dieker, V. Shneer Large deviations for random walks under subexponentiality: The big-jump domain The Annals of Probability, Ann. Probab. 36(5), 1946-1991 (2008).
S. Foss, D. Korshunov, S. Zachary, An Introduction to Heavy-Tailed and Subexponential Distributions. Vol. 6. New York: Springer, 2011.
I. Kortchemski. Limit theorems for conditioned non-generic Galton–Watson trees. Annales de l'I.H.P. Probabilités et statistiques, Tome 51 no. 2, pp. 489-511 (2015).
J.-F. Le Gall Random trees and applications., Probability Surveys 2 (2005): 245-311.