STAT 206B: Reversible Markov Chains and Random Walks on Graphs (Spring 2004)

Instructor David Aldous

Class time WF 1.00 - 2.30 (room 1011 Evans Wednesdays, room 340 Evans Fridays).

Topics

The course is based on the draft book Reversible Markov Chains and Random Walks on Graphs available online. Another useful resource is a monograph by Mark Jerrum Counting, Sampling and Integrating: Algorithms and Complexity (scroll down that page)

Prerequisites

STAT 205A is helpful but not totally necessary; upper-division level probability theory is assumed. Some prior knowledge of Markov chains is helpful; note that first 5/6 weeks of STAT 205B will do the rigorous theory of countable-state Markov chains.

Grading Students taking the course for credit are expected to read a research paper and present it in class (25 minutes) during the final 3 weeks of classes.

Office Hours

David Aldous (aldous@stat) Mondays 1.00-3.00 in 351 Evans

Some suggested papers for student talks

(But even better if you choose a different paper related to your own interests).

Eric Vigoda's homepage has several interesting papers, in particular randomly coloring constant degree graphs.

Alistair Sinclair's homepage has several interesting papers, in particular fast mixing for independent sets, colorings, and other models on trees and random walks on truncated cubes and sampling 0-1 knapsack solutions.

Laszlo Lovasz home page , under research papers: random walks and volume computations, has many interesting papers such as "hit and run mxies fast" and "the geometry of logconcave functions". Also see survey papers: "Mixing times".

Perfect sampling is an interesting topic; many references are at David Wilson's web site.

Ravi Kannan's home page under "Markov chains" has papers such as "rapid mixing of several Markov chains for a hard-core model".

Below are two survey papers (can't find online but I have copies) from which interesting topics could be extracted

Relaxation times of Markov chains in statistical mechanics and combinatorial structures (F. Martinelli)
Random walks on finite groups (L. Saloff-Coste)

Student talks

25 minute talks.

Wednesday April 28

Talk by Vince Vu. Mixing Times by L. Lovasz and P. Winkler.
Talk by Kamalika Chaudhuri. Random walks and an O(n^5) volume algorithm for convex bodies by Lovasz, Kannan and Simonovits.
Talk by Yumi Odama. Exact Sampling with coupled Markov chains and applications to statistical mechanics by J. Propp and D.B. Wilson.

Friday April 30

Talk by Kenji Obata. Random walk on truncated cubes and sampling 0-1 knapsack solutions by Ben Morris and Alistair Sinclair.
Talk by David Pokorny. Fast mixing for independent sets, colorings and other models on trees by Alistair Sinclair et al.
Talk by Zegang Zhu. Randomly coloring constant degree graphs by E. Vigoda et al.

Wednesday May 5

Talk by Shankar Bhamidi. Iterated random functions by Persi Diaconis and David Freedman.
Talk by Rui Dong. The Asymmetric one-dimensional constrained Ising model by D. Aldous and P. Diaconis.
Original talk by Georgios Dimakis. Random walks on sensor networks.

Friday May 7: time 1.10 - 3.20

Talk by Mikhail Traskin. Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains by M. Jerrum et al.
Talk by Sebastien Roch. Convergence of the iterated prisoner's dilemma game by Martin Dyer et al.
Talk by Gabor Pete. Random walks on infinite groups: boundary and entropy. Based on papers by A. Vershik and V. Kaimanovich.
Talk by Peter Ralph Evolving subsets. Based on paper of Peres and Morris.
Talk by Lionel Levine Minimization algorithms on the d-cube.