- Combinatorial estimates; Cramer's and Sanov's theorems, analogs for Markov chains, in finite-dimensional vector spaces and then in more abstract set-up. This part relates to exact asymptotics, moderate deviations, martingale differences and concentration inequalities.
- General large deviations principles such as existence, uniqueness, contractions and metrizability. Role of Fenchel-Legendre transform and Varadhan's integration lemma in identifying the rate function.
- Large deviations for stochastic processes: random walks, Brownian motion and diffusion processes, exit from domain problems.

- Probabilistic analysis of classical Euclidean optimization problems (Traveling Salesman, Minimum Spanning Tree, Minimum Matching) using subadditivity and elementary concentration inequalities.
- Uses of Talagrand's isoperimetric theory for proving concentration inequalities.

**Office Hours:** Tu 1.45 - 3.45pm in 351 Evans.

If you email me (aldous@stat) put "STAT 206" in subject line.

** Requirements for students.**
Students taking course for credit need to do one of the following.

- Exercises from the Large Deviations text. Do 10 problems out of 2.1.21, 2.1.28, 2.2.23, 2.2.26, 2.2.37, 2.2.39. 2.3.17, 2.3.25, 2.3.27, 3.7.11(a), 4.1.31, 4.1.32. 4.3.12, 6.1.16, 6.2.17, 6.2.27, 5.2.12.
- Read a recent research paper (suggestions below and present in class as a 25 minute talk (final week of course).
- Do some little research project (suggestions below).

1/22 - 1/29: 1.1, 1.2, 2.1.1, 2.1.2

1/31 - 2/5: 2.2

2/7: 2.3

2/12: 3.1.1, 3.1.2

2/14: 3.1.3, 3.2

2/19: 3.3

2/19 - 2/21 : 3.6

2/26: 5.1

2/28: 5.2, 5.6.

3/4: 5.7

3/6: 6.1

3/13: easy random TSP lower bound; Azuma's inequality and method of bounded differences; direct application to LCS, less direct application to TSP.

3/18: Subadditivity proof of TSP result -- LLN for EL_n. Emphasising determinstic upper/lower bounds on partitioned space, and Poissonization.

3/20: General "subadditive Euclidean functionals" set-up. Hamming isoperimetric inequality. Rhee's concentration inequality.

4/1: Talagrand's convex distance isoperimetric inequality. Application to Steiner trees. Space-filling curve heuristic for TSP.

4/3: Concentration inequality for TSP. Percolating Paths through Random Points. Illustrates indirect use of subadditivity and optimization under constraint.

4/8 : Maximum weight matchings on random trees, sec. 3 of The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence, as introduction to probabilistic reformulation of cavity method.

4/10: Flow through a randomly obstructed network (sec 3.6 of this paper) as illustration of heuristic cavity method.

M 4/14 - F 4/18: no class

Tu 4/22 : Optimal flow through the disordered lattice.

Th 4/24 - Tu 4/29 : Examples from Probability Approximations via the Poisson Clumping Heuristic. General setup. Covering by random squares. Hitting times for one-dimensional diffusions. Near misses of randomly moving particles.

- [Chris Haulk] : Large deviations for processes with independent increments by A.A. Mogulskii.
- [Partha Day] : Precise large deviation estimates for a one-dimensional random walk in a random environment by A. Pisztora and T. Povel and O. Zeitouni.

- [Xuening Sun] : Estimation of the Number of Operating Sensors in Large-Scale Sensor Networks with Mobile Access by Cristian Budianu, Shai Ben-David, and Lang Tong.
- [Tanya Gordeeva] : Large deviations for functionals of spatial point processes with applications to random packing by T Schreiber and JE Yukich.

- [Javet Ahmed] : Large Deviations and the distribution of price changes by Laurent Calvert and Adlai Fisher.
- [Jian Ding] : Sample path large deviations for queues with many inputs by Damon J. Wischik.
- [Madhur Tusliani] : Short-length routes in low-cost networks via Poisson line patterns by Kendall - Aldous.

- Large deviations and stochastic calculus for large random matrices by Alice Guionnet.
- Large deviations associated with Poisson--Dirichlet distribution and Ewens sampling formula by Shui Feng.
- Source coding, large deviations, and approximate pattern matching by Dembo and Kontoyiannis.
- How T-cells use large deviations to recognize foreign antigens by Ellen Baake, Frank den Hollander, Natali Zint.

- Limit theorems for maximum flows on a lattice by Yu Zhang.