LARGE DEVIATIONS and STOCHASTIC SPATIAL OPTIMIZATION
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
- 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.
(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.
-
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.
Finally I will talk about some of my own recent work in this area
and open problems suitable for thesis projects.
Administration
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.
- 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).
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.