Markov chains: mixing times, hitting times, and cover times

One aim of the course is to describe the close connections, some old and some new, between three basic parameters of a Markov chain: Mixing time, hitting time and cover time. In particular, following classical results of Aldous, recent work ([2] and independently, [3]) shows that mixing time is equivalent to the maximal hitting time of large sets. Another aim is to present some useful methods for analyzing a Markov chain, namely coupling, stationary stopping times, optional stopping for suitable martingales, and the spectrum. Key examples will include random walks on the symmetric group (card shuffling), Glauber dynamics for the Ising model, and lamplighter groups. We will also describe the connection [6] of the cover time to the maximum of the Gaussian Free Field.

Open problems we will explore are:

1. Diaconis’ challenge to understand which chains exhibit cutoff (an abrupt change of the total variation distance to stationarity from near 1 to near zero).
2. for Glauber dynamics, when do extra updates assist mixing, and how do random updates compare with systematic updates?
3. On a Cayley graph, for how long is the rate of escape at least the square root of t/d,where t denotes time and d is the degree?
4. On a transitive graph, is mixing time always bounded above by the diameter squared times the degree?
5. In what generality is the diameter squared divided by log(n) a lower bound for the mixing time on an n-vertex graph?

References:

1. Markov Chains and Mixing Times, (2008). David A. Levin, Yuval Peres and Elizabeth L. Wilmer. Published by the Amer. Math. Soc., See http://research.microsoft.com/en-us/um/people/peres/markovmixing.pdf (errata are at http://pages.uoregon.edu/dlevin/MARKOV/errata.pdf)
2. Mixing times are hitting times of large sets. Yuval Peres, Perla Sousi http://arxiv.org/abs/1108.0133
3. Mixing and hitting times for finite Markov chains. Roberto Imbuzeiro Oliveira. http://front.math.ucdavis.edu/1108.1708
4. Can extra updates delay mixing? Yuval Peres, Peter Winkler http://arxiv.org/abs/1112.0603
5. Harmonic maps on amenable groups and a diffusive lower bound for random walks (2009). James R. Lee, Yuval Peres Ann. Probability, to appear. http://arxiv.org/abs/0911.0274
6. Cover times, blanket times, and majorizing measures (2010) Jian Ding, James R. Lee, Yuval Peres http://arxiv.org/abs/1004.4371

Курс прочитан в рамках St. Petersburg School in Probability and Statistical Physics.

Источник информации