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:

Chapter 1: Large deviations in the Cramer regime

Chapter 2: The one-big jump phenomenon

Chapter 3: Application to random trees

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.

Introduction

Chapter 1: Large deviations in the Cramer regime (updated 14/03)

Chapter 2: The one big jump phenomenon (updated 16/05: condition E[X^2 1_{X<=0}]<∞ added in (H_Δ) page 2, to ensure finite variance) (updated 26/07: page 7 it was implictly assumed that the law of X_1 was discrete; the general case is essentially the same and has been added).

Chapter 3: Application to random trees (updated 30/05)

Limits of large random trees (slides of the last lecture)

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)
6	18.04.24	Proof of the theorem in 2) (except the small final part).	Chapter 2 (pages 3-4)
7	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)
8	2.05.24	Plane trees, coding by the Lukasiewicz path, Bienaymé trees and the connection with random walks.	Chapter 3 (pages 1-4)
9	16.05.24	Critical Bienaymé trees and exponential tilting, cycle lemma, probabilistic consequences.	Chapter 3 (pages 5-8)
10	30.05.24	Vervaat transform, condensation in heavy-tailed subcritical Bienaymé trees	Chapter 3 (pages 8-10), slides.

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.

Exercise 1 (for February 29th) - Solution

Exercise 2 (for March 7th) - Solution

Exercise 3 (for March 14th) - Solution

Exercise 4 (for April 11th) - Solution

Exercise 5 (for April 18th) - Solution

Exercise 6 (for April 25th) - Solution

Exercise 7 (for May 2nd) - Solution

Exercise 8 (for May 16th) - Solution

Exercise 9 (for May 23rd; postponed to May 30th) - Solution

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

(update 22/05) The format of the oral exam will be the following: I will be give you a list of three exercices among the exercises above, and you will be asked to solve the exercise of your choice among these three exercises.

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).