STAT C206A (= MATH C223A): Reversible Markov Chains and Random Walks on Graphs (Fall 2011)
Instructor: David Aldous
Class time: MW 5.006.30 in room 3113 Etcheverry.
Office Hours: Thursdays 1.003.00 in 351 Evans
email: aldous@stat.berkeley.edu (put "STAT 206" in subject)
Prerequisites
STAT 205AB is helpful but not really necessary; upperdivision 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 blackboardandchalk, 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
(AldousFill) and on the (print and online) book
Markov Chains and Mixing Times
(LevinPeresWilmer).
Also useful is the monographlength paper
Mathematical Aspects of Mixing Times in Markov Chains
(Montenegro  Tetali).
Classbyclass schedule
The overall plan for the first 1/3 of the course is to start off with the interesting
parts of chapters 24 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 cointossing. 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: Timereversed chain, catandmouse 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; setup, dense graphs, dcube, graph coloring.
(RWG Chap 43, sec 1.11.5).
 9/28: Pathcoupling. Extensions of partial order (example)
(RWG Chap 43, sec 1.121.13.

 10/3: Approximate counting, illustrated by graphcoloring. Coupling for random
transpositions.
 10/5: Examples of lowerbounding tau_2 via test functions. Projection lemma.
Product chains. (RWG Chap 4.6.2).

 10/10: RW on the dcube {0,1}^d and the ddimensional 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 writeup and the Schweinberg paper and a
hard open problem.
 10/19: Ising model. (MCMT Chapter 15.1).

 10/24: Bottlenecks, relaxation time and Cheegertype 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. Metropolisstyle chains. Lowtemperature behavior.
(latter is this note).
 11/2: Diffusion heuristic for optimal scaling of highdimensional Metropolis.
(RWG Chap MCMC sec 5).

 11/7: EfronStein inequalities; CarneVaropoulos large deviation bound.
(RWG 4.6.3 and Carne A transmutation formula for Markov chains).
 11/9: Are you related to your ancestors;
aggregationfragmentation models (second is this note).

 11/14: Two results for nonreversible chains: mimimal stopping times and
the matrixtree 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