STAT C206A (= MATH C223A): Reversible Markov Chains and Random Walks on Graphs (Fall 2011)
Instructor: David Aldous
Class time: MW 5.00-6.30 in room 3113 Etcheverry.
Office Hours: Thursdays 1.00-3.00 in 351 Evans
email: aldous@stat.berkeley.edu (put "STAT 206" in subject)
Prerequisites
STAT 205AB is helpful but not really necessary; upper-division level
probability theory and some prior knowledge of finite Markov chains is assumed.
Grading:
Students taking the course for credit are expected to
read a research paper and present it in class (16 minutes)
during the final 3 weeks of classes.
Talks can be blackboard-and-chalk, or a laptop presentation.
Here is a list of possible papers to read.
More papers can be found by doing a Google Scholar search of citations to the books below.
I encourage you to choose something related to your own interests.
Topics
The course is based on the online draft book
Reversible Markov Chains and Random Walks on Graphs
(Aldous-Fill) and on the (print and online) book
Markov Chains and Mixing Times
(Levin-Peres-Wilmer).
Also useful is the monograph-length paper
Mathematical Aspects of Mixing Times in Markov Chains
(Montenegro - Tetali).
Class-by-class schedule
The overall plan for the first 1/3 of the course is to start off with the interesting
parts of chapters 2-4 of RWG, which is comparatively classical, and then
turn to the first few chapters of MCMT with emphasis on the specific examples discussed there.
- 8/29:
Basics of finite chains. Occupation measure and mean hitting time formulas.
(RWG 2.1, 2.2).
- 8/31: Variance of sums, CLT. Patterns in coin-tossing. Variation distance and d(t)
for MCs. (RWG 2.3, 2.4.1).
-
- 9/7: Cover times and Matthews' method; martingale techniques. (RWG 2.6, 2.8).
-
- 9/12: Time-reversed chain, cat-and-mouse games, reversible MC = RW on weighted
graph. (RWG 3.1 - 3.2).
- 9/14: Electrical network correspondence, spectral representation. (RWG 3.3 - 3.4).
-
- 9/19:
Complete monotonicity (brief); L^2 setup and Dirichlet form;
the 3 extremal characterizations; contraction lemma.
(RWG 3.5.0, 3.6.1, 3.6.2).
- 9/21: Big Picture; 4 parameters and some relations. (parts of RWG 4.1 - 4.3).
Exponential approx for hitting times (RWG 3.5.4).
-
- 9/26:
Coupling; set-up, dense graphs, d-cube, graph coloring.
(RWG Chap 4-3, sec 1.1-1.5).
- 9/28: Path-coupling. Extensions of partial order (example)
(RWG Chap 4-3, sec 1.12-1.13.
-
- 10/3: Approximate counting, illustrated by graph-coloring. Coupling for random
transpositions.
- 10/5: Examples of lower-bounding tau_2 via test functions. Projection lemma.
Product chains. (RWG Chap 4.6.2).
-
- 10/10: RW on the d-cube {0,1}^d and the d-dimensional torus Z_m^d. (RWG 5.2).
- 10/12: RW on Z_m^d and Z^d (continued). The distinguished paths method for
upper bounding \tau_2. (RWG Chap 4.4.3).
-
- 10/17: Example: a RW on cladograms.
My write-up and the Schweinberg paper and a
hard open problem.
- 10/19: Ising model. (MCMT Chapter 15.1).
-
- 10/24: Bottlenecks, relaxation time and Cheeger-type inequalities.
(RWG 4.51. - 4.5.2; MCMT 13.3).
- 10/26: Evolving sets and mixing times. (MCMT sec 17.4).
-
- 10/31: Examples of Cheeger. Metropolis-style chains. Low-temperature behavior.
(latter is this note).
- 11/2: Diffusion heuristic for optimal scaling of high-dimensional Metropolis.
(RWG Chap MCMC sec 5).
-
- 11/7: Efron-Stein inequalities; Carne-Varopoulos large deviation bound.
(RWG 4.6.3 and Carne A transmutation formula for Markov chains).
- 11/9: Are you related to your ancestors;
aggregation-fragmentation models (second is this note).
-
- 11/14: Two results for non-reversible chains: mimimal stopping times and
the matrix-tree theorem. (RWG Chap 9.1, 9.2.1).
Student talks
Wednesday 11/16
Monday 11/21
Wednesday 11/23 No class
Monday 11/28
Wednesday 11/30
Monday 12/5