STAT C206B [= MATH C223B], Spring 2008: David Aldous

STAT 206, with catalog description Stochastic Processes, is intended to have a different subject each semester. So STAT 206A is not a prerequisite. I will teach two separate topics.

Large Deviations

For students intending to do research in mathematical probability, it's good to get to grips with technical aspects of some substantial area. In the first half of the course I will follow parts of Large Deviations Techniques and Applications by Amir Dembo and Ofer Zeitouni. We cover topics such as (Acknowledgement: material copied from Amir Dembo's Stanford course).

Optimal structures over random spatial or combinatorial data

This is a small field which studies mathematical properties of (rather than algorithms for finding) solutions of optimization problem over random points in space or random combinatorial structures. I will start by following parts of Probability Theory and Combinatorial Optimization by J. Michael Steele. Finally I will talk about some of my own recent work in this area and open problems suitable for thesis projects.


Lecture times: TuTh 11.00 - 12.30 in room 334 Evans.

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.

Large deviations [sections from text]

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

Optimal structures over random spatial or combinatorial data

3/11: Overview of probability and algorithms. TSP on random points as paradign example of "Optimal structures over random spatial or combinatorial data". Longest common subsequece (LCS) as simpler example. Use of subadditivity, elementary inner/outer bounds in LCS. Bound on worst-case TSP length.

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.

Student talks

Thursday May 1 Tuesday May 6 Thursday May 8

Other possible talk topics

There are papers studying large deviations within almost any kind of probability model you can imagine. Indeed Google Scholar will show you 1772 papers citing Dembo-Zeitouni. Here are just a few. Scattered papers related to the second half of the course.