MATH289A Topics in Probability/Statistics:

Markov chains and mixing times, Spring 2017

This course is an introduction to the theory of Markov chain mixing times, which measure how long it takes for a Markov chain to get close to its stationary measure. Markov chains are useful in Monte Carlo simulation, with applications in areas such as statistical physics, approximate counting, and combinatorial optimization. The mixing time can determine the running time for simulation. 

We will start with the basis of the theory, then introduce geometric methods (isoperimetric inequalities, spectral profile,…) and probabilistic methods (such as path coupling, evolving sets) to estimate mixing times. We will cover some further L_2 methods such as comparison of Dirichlet forms and Wilson’s lower bound from eigenfunctions. If time permits we will also discuss applications to Ising model (spatial mixing and phase transition) and some examples of Markov chains where the cutoff phenomenon is understood. 

Instructor:

Tianyi Zheng (tzheng2@math.ucsd.edu) 

Lectures:

2:00-2:50PM on Mondays, Wednesdays, and Fridays in AP&M 2402. 

Office Hours:

Wednesdays 4-6pm in AP&M 6202.

Grading:

To receive letter grade for this course, near the end of the quarter present a topic in class for 20-30 min.

References:

We will draw topics mostly from the following two sources:

1. D. Levin, Y. Peres, and E. Wilmer. Markov chains and mixing times. American Mathematical Soc., 2009.

This book is available here on D. Levin’s webpage.

2. L. Saloff-Coste. Lectures on finite Markov chains.

Here is the link to Springer.

Additional papers and notes will be posted here during the quarter.

Tentative Schedule (to be updated):

Week 1: Introduction to mixing times. Bounds using eigenvalues.

Week 2:

Some elementary lower bounds (Section 7.1, 7.3 in Reference 1).

Dirichlet forms (Section 2.1 in Reference 2).

Simple comparison of chains (Section 4 in Reference 2, Section 13.3 in Reference 1).

Week 3:

Bottleneck ratio, Cheeger inequality (Section 13.2 in Reference 1)

Brief detour to return probability of random walks on infinite graphs. Based on Coulhon-Grigor’yan theory. Reference:

Coulhon, T. "Ultracontractivity and Nash type inequalities." Journal of functional analysis 141.2 (1996): 510-539.

Coulhon, T., Grigor'yan, A. and Pittet, Ch. "A geometric approach to on-diagonal heat kernel lower bounds on groups." Annales de l'institut Fourier. Vol. 51. No. 6. 2001.

Week 4:

Spectral profile:

Goel, S., Montenegro, R., & Tetali, P. (2006). Mixing time bounds via the spectral profile. Electron. J. Probab, 11(1), 1-26.

Evolving sets method (Chapter 17 in Reference 1).