Condensation Phenomena in Random Trees Spring 2024
- Lecturer
- Igor Kortchemski
- Course Catalogue
- 401-4614-24L
Content
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. The goal of the course is to 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 will be a key tool for studying this phenomenon. Finally, we shall discuss applications of these results to other combinatorial models.
Outline of the course:
Lectures
Lectures will take place in-person at HG D 3.2 on Thursdays from 08:15 to 10:00, starting on 22.02 and finishing on 30.05.
No class on March 21st nor March 28th.
Video recordings
Lectures will be recorded and uploaded to the ETH Video Portal (the use of full-screen mode with at least 1080p quality is recommended for optimal readability of the blackboard).
Lecture notes
Lecture notes will be made available after each session. The notes are copyright protected and may not be circulated without permission.
Diary of the lectures
Detailed lecture overview (click to expand)
| no. | date | content | references (lecture notes) |
|---|---|---|---|
| 1 | 22.02.24 | Introduction, first observations, statement of Cramer's theorem. | Introduction, Chapter 1 (pages 1-3) |
| 2 | 29.02.24 | Proof of Cramer's theorem, behavior under the conditional law | Chapter 1 (pages 3-5) |
| 3 | 7.03.24 | Lattice random variables, statement of the local central limit theorem, application to asymptotics of local probabilities | Chapter 1 (pages 6-8) |
| 4 | 14.03.24 | Behavior under local conditional probabilities, proof of the local central limit theorem. | Chapter 1 (pages 9-11) |
| 5 | 11.04.24 | Maximal inequality, H_Δ condition. | Chapter 2 (pages 1-2) |
| 5 | 18.04.24 | Proof of the theorem in 2) (except the small final part). | Chapter 2 (pages 3-4) |
| 6 | 25.04.24 | End of the proof of the theorem in 2), proof of the one big jump principle and its corollary. | Chapter 2 (pages 4-7) |
| 6 | 25.04.24 | Plane trees, coding by the Lukasiewicz path, Bienaymé trees and the connection with random walks. | Chapter 3 (pages 1-4) |
Exercises
An exercise is often given for the next lecture. You are encouraged to think about it (this helps to keep up with the pace of the course).
PhD students who want to get credits, should upload their work (solutions may be incomplete) using the following link (before the given date): Upload link. Please name the created file as {name}_{exercise number}.pdf (e.g. andrey.kolmogorov_1.pdf).
(update 15/03) Only D-Math and I-Math doctoral students can enrol for the DRL-module and thus, do a „ungraded semester performance“. Doctoral students from other departments enrol for the standard module and have to do the exam as Math master students have to.
Exam
Please note for students taking the exam that the exam for this course will be oral. Further information is found in the course catalogue
Additional 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).