## 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