ISI logo

Lectures on Probability and Stochastic Processes X

Indian Institute of Science
December 13 - 16, 2015

IISc logo

Markov chains: Mixing time, cover time, and rate of escape by Yuval Peres, Microsoft Research, Redmond, U.S.A.
Suggested references for background material:

Lecture 1: The rate of escape.
Abstract: How fast does a random walk escape from its starting point? We will discuss several approaches to this question: Using the spectrum, the Ergodic Theorem, Varopolous-Carne long-range bounds and Markov type of Metric spaces. We will also see how the rate of escape is related to the minimal distortion with which the underlying graph can be embedded in Euclidean space. Ref: Carne, Bull. Sci. Math 109 (1985); Chapter 13 of Lyons and Peres.

Lecture 2: Mixing and rate of escape.
Abstract: Before a random walk escapes from the neighborhood of its starting point, it cannot mix. This simple observation can be combined with estimates on rate of escape to give useful lower bounds for the mixing time. Using escape rate to prove matching upper bounds on mixing time is more delicate; I will describe a method developed with James Lee that is a step in this direction. Ref: Lee and Peres, Ann. Probab. 41 (2013), 3392–3419.

Lecture 3: Strong stationary times, Evolving sets and the expansion profile.
Abstract: After reviewing the basics of strong stationary times, I will discuss evolving sets, a set-valued chain developed in 2004 with Ben Morris, closely related to work of Diaconis-Fill (Ann. Probab. 1990). This process can yield upper bounds on mixing time via the expansion profile of the graph and can also be used to analyze walks on graphs that change over time. Ref: Aldous and Diaconis, Adv. Appl, Probab 8 (1987), 69-97 ; Morris and Peres, PTRF 133 (2005), 245–266.

Lecture 4: Mixing times and hitting times.
Abstract: For lazy reversible chains, the mixing time is within a constant factor of the maximal hitting time of “large” sets. The original proof of this, obtained in joint work with P. Sousi and independently by R. Oliviera, relied on ideas of D. Aldous involving stationary stopping times.

I will describe a more recent approach (developed jointly with R. Basu and J. Hermon) that relies on maximal inequalities instead, and yields tighter bounds. The connection between mixing and hitting times implies that for trees, the mixing time is robust under small changes in the edge conductances.

It is an open problem to determine if the same property holds for all transitive graphs. Ref: Peres and Sousi, J. Th. Probab 2013 ; Basu, Hermon and Peres (SODA 2015); Annals of Probability, to appear.

Lecture 5: Cutoff on all Ramanujan Graphs.
Abstract: Lubotzky, Phillips, and Sarnak (1988) defined a connected $d$-regular graph $G$ (with $d>2$) to be Ramanujan iff for every eigenvalue $\lambda$ of its adjacency matrix, its absolute value is either $d$, or at most $2\sqrt{d-1}$. We show that on every Ramanujan graph $G$ with $n$ vertices, simple random walk exhibits cutoff: the mixing time in total-variation is asymptotic to $[d/(d-2)] \log_{d-1} n$. Furthermore, for all $p$ in $[1,\infty]$, the $d$-regular Ramanujan graphs minimize the asymptotic $L^p$-mixing time among all $d$-regular graphs. In particular, this gives the first examples of transitive expanders with cutoff.

Our proof also shows that, for every vertex $x$ in an $n$-vertex Ramanujan graph $G$, its distance from $n-o(n)$ of the vertices in $G$ is asymptotically $\log_{d-1} n$.

The key to our proofs is a precise spectral analysis of the non-backtracking walk. (Joint work with Eyal Lubetzky, NYU)

Lecture 6: Random walk on the random graph
Abstract: I will discuss the behavior of the random walk on two random graph models: on one hand the random regular graph with constant degree, and on the other hand the giant component of the supercritical Erdos-Renyi random graph with constant average degree. In the former case it is known that the walk mixes in logarithmic time and exhibits the cutoff phenomenon. In the latter case, while starting from the worst initial state delays mixing and precludes cutoff, it turns out that starting from a typical vertex induces the rapid mixing behavior of the regular case. (Joint work with Nathanael Berestycki, Eyal Lubetzky and Allan Sly.)

Lectures 7-8: Cover times, blanket times, and the Gaussian free field.
Abstract: The cover time of a finite graph $G$ (the expected time for simple random walk to visit all vertices) has been extensively studied, yet a number of fundamental questions concerning cover times have remained open: Aldous and Fill (1994) asked whether there is a deterministic polynomial-time algorithm that computes the cover time up to an $O(1)$ factor; Winkler and Zuckerman (1996) defined the blanket time (when the empirical distribution of the walk is within a factor of $2$, say, of the stationary distribution) and conjectured that the blanket time is always within $O(1)$ of the cover time. The best approximation factor found so far for both these problems was $(\log \log n)^2$ for n-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).

We show that the cover time of G, normalized by the number of edges, is equivalent (up to a universal constant) to the square of the expected maximum of the Gaussian free field on G. We use this connection and Talagrand's majorizing measure theory to deduce a positive answer to the question of Aldous-Fill (1994) and establish the conjecture of Winkler-Zuckerman (1996). All these results extend to arbitrary reversible finite Markov chains.

Lecture based on the paper: Ding, Jian; Lee, James R.; Peres, Yuval. Cover times, blanket times, and majorizing measures. Ann. of Math. (2) 175 (2012), no. 3, 1409–1471.