MA 396: Theory of large deviations and related topics (Fall 2019)


Instructor: Anirban Basak
Email: anirban.basak@icts.res.in
Office location: L-14, IISc Mathematics Department.
Office hours: By appointment.
Class time and location: TuTh 2.00-3.30 PM, LH-3, IISc Mathematics department. First class is on August 01.
Prerequisite: This is a graduate level topics course in probability theory. Graduate level measure theoretic probability will be useful, but not a requirement. The course will be accessible to advanced undergraduates who have had sufficient exposure to probability.
Course outline: Large deviations provide quantitative estimates of the probabilities of rare events in (high-dimensional) stochastic systems.
The course will begin with general foundations of the theory of large deviations and will cover classical large deviations techniques such as Sanov's Theorem, Cramér's Theorem, Gärtner-Ellis Theorem, Contraction principle, Varadhan's Integral Lemma, and Bryc's Inverse Varadhan Lemma.
The latter half of the course will focus on some recent developments. Topics include large deviations in the context of random matrices, large deviations for subgraphs counts in random graphs (both dense and sparse regime), nonlinear large deviations, and low complexity of Gibbs measures. If time allows selected topics from Spin Glasses will be introduced.

Suggested books:
1. Amir Dembo and Ofer Zeitouni, Large Deviations Techniques and Applications.
2. Firas Rassoul-Agha and Timo Seppäläinen, A Course on Large Deviations with an Introduction to Gibbs Measures.
3. Marc Mézard and Andrea Montanari, Information, Physics, and Computation.
4. Sourav Chatterjee, Large Deviations for Random Graphs.

Tentative Weekly Schedule:
Aug 01: Course outline and examples.
Aug 06 and 08: Examples (continued), Sanov's Theorem for finite alphabet, properties of lower semicontinuous functions.
Aug 13: Sanov's Theorem for finite alphabet (continued).
Aug 20 and 22: Cramér's Theorem in \(\mathbb{R}\), large deviations for sums of i.i.d. random variables beyond the scope of Cramér's Theorem.
Aug 27 and 29: Cramér's Theorem in \(\mathbb{R}\) (continued), weak large deviations principle, Cramér's Theorem in \(\mathbb{R}^d\).
Sep 03 and 05: Weak large deviations principle and Cramér's Theorem in \(\mathbb{R}^d\) (continued), Gärtner-Ellis Theorem.
Sep 12: Gärtner-Ellis Theorem (continued), large deviations for the flow of current.
Sep 17 and 19: Large deviations for the flow of current (continued), exponential equivalence, contraction and inverse contraction principles.
Sep 24 and 26: No lectures.
Oct 01 and 03: Varadhan's Integral Lemma, Bryc's Inverse Varadhan Lemma, Curie-Weiss Ising spin model: free energy.
Oct 10: Curie-Weiss Ising spin model (continued): large deviations of the magnetization and analysis of the fixed point equation.
Oct 15 and 17: Examples of nonlinear large deviations, large deviations of the upper tail of nonlinear functions of i.i.d. random variables.
Oct 22 and 24: Large deviations of the upper tail of triangle counts in sparse Erdős-Rényi graphs using Chatterjee-Dembo framework, naïve Mean-Field approximation for partition functions.
Oct 29 and 31: Naïve Mean-Field approximation for Ising on general graphs.
Nov 05 and 07: Locally tree-like graphs, belief propagation and Bethe free entropy for factor models on finite graphs and trees.
Nov 12 and 14: No lectures.
Nove 19 and 21:

Grading: Students taking this course for credit are required to do a (reading) project, submit a report, and give a presentation on the same at the end of the semester. Depending on the number of registered students the grading scheme may change.


References on large deviations for sums of stretched exponential random variables:
A. V. Nagaev, Integral Limit Theorems Taking Large Deviations into Account when Cramér’s Condition Does Not Hold.
N. Gantert, K. Ramanan, and F. Rembart, Large deviations for weighted sums of stretched exponential random variables.
Reference on the necessity of \(0 \in {\mathcal D}_\Lambda^\circ\) in Cramér's Theorem on \(\mathbb{R}^d\) with \(d \ge 2\):
I. H. Dinwoodie, A Note on the Upper Bound for I.I.D. Large Deviations.
References on large deviations of subgraph counts in sparse Erdős-Rényi graphs: