MARKOV CHAINS AND MIXING TIMES COURSE

The main component in the running time of the MCMC algorithm is the “mixing time” of the underlying Markov chain., i.e., the number of steps one needs to run the chain to approximate the stationary distribution well.

Welcome to the webpage of this course on Markov chains and mixing times. The course starts with material from the book https://www.yuval-peres-books.com/markov-chains-and-mixing-times/ and will continue with more advanced material based on recent research. As the course progresses, we will include here lecture notes and links to lecture videos.

Lectures

Last uploaded: Lecture 2 (Week 10)
Week 1: Basic definitions and examples

1.1.  Why Markov Chains?

1.2. Random Mapping Representation 

1.3. Irreducibility and Aperiodicity 

1.4. Random Walks on Graphs 

1.5. Stationary Distributions 

1.6. Reversibility  

1.7. Eulerian graphs
1.8. Harmonic functions

1.9. Gambler's Ruin

Week 2: Mixing, coupling and stationary times

2.1. Time Reversals

2.2. Coupon Collecting

2.3. Total Variation Distance and coupling

2.4. The Convergence Theorem

2.5. Mixing in total variation
2.6. Mixing via coupling

2.7. The cycle and the Hypercube
2.8. Stationary Times
2.9. Strong Stationary Times and separation distance 

Week 3: Separation distance and lower bounds

3.1. Top-to-Random Shuffle

3.2. Optimal strong stationary times

3.3. Comparing separation distance and total variation

3.4. Birth and death chains

3.5. A markov chain from linear algebra 
3.6. Counting and diameter lower bounds 
3.7. Bottleneck Ratio 

Week 4: Riffle shuffles, Random Walks and electrical networks

4.1. Riffle shuffles
4.2.Networks and Reversible Markov Chains  

4.3. Voltages and Current Flows 

4.4. Computing effective resistance
4.5. Thomson's principle
4.6. Nash-Williams inequality
4.6. Commute Time 

Week 5: From hitting times to Cover Times

5.1. Bounding Mixing Times via Hitting Times
5.2. Eigenvalues

5.3. Matthews' bounds for cover time
5.4. Varopolous-Carne long range inequality

5.5. A stronger diameter lower bound for mixing time

Week 6: Eigenvalues and path coupling

6.1. The Spectral Representation of a Reversible Transition Matrix 

6.2. The Relaxation Time

6.3. The Dirichlet Form and the Bottleneck Ratio 

6.4. Comparison of Markov Chains 

6.5. Expander Graphs 
6.6. The Transportation metric
6.7. Path Coupling  
6.8. The Ising model 

 

Week 7: The Ising Model

7.1. A topological obstruction for the Ising model
7.2. Open problem: Monotonicity of relaxation time
7.3. Monotonicity of top eigenfunction
7.4. Harris' inequality
7.5. Positive correlations for the Ising model

Week 8: Bounds for Glauber dynamics mixing time

8.1. Eigenvalues for Glauber dynamics are non-negative
8.2. A uniform lower bound for mixing time of Ising-Glauber dynamics
8.3. Lower bound for the trace of a transition matrix
8.4. The 3-1 tree
8.5. Proving fast mixing for Potts model via contraction
8.6. Swendsen-Wang dynamics and the random cluster model

Week 9: Isoperimetric inequalities, Entropy and Martingales

9.1. Discrete Isoperimetric inequalities
9.2. Entropy
9.3. More on Random cluster model
9.4. Doob transform of a Markov chain
9.5. Martingales
9.6. Waiting time for a pattern

Week 10: Evolving sets

10.1. Evolving sets and mixing
10.2. A stratified walk on the hypercube
10.3. Finding sparse cuts via evolving sets

Week 11: Modified hypercube walks and estimating graph parameters

11.1. A stratified walk on the hypercube
11.2. Estimating graph parameters via random walks 
11.3. Mixing for monotone subsets of hypercube

Week 12: Cutoff and Ramanujan graphs

12.1. The cutoff phenomenon
12.2. Ramanujan graphs

Week 13: Random walks on the random graph

13.1. Random walks on the random graph

Yuval Peres

About Yuval Peres

Yuval Peres is a mathematician working in probability theory and its interface with computing, PDE, game theory, and machine learning.
He has coauthored six books, available at https://www.yuval-peres-books.com/ and mentored more than twenty PhD students, see https://www.genealogy.math.ndsu.nodak.edu/id.php?id=22523 Many of these students are leading researchers in universities such as MIT, Toronto, Tel Aviv, Peking University, University of Oregon, T.U. Munich etc.
Yuval's best known results concern the fine properties of Random walks and Brownian motion, especially cover time and thick points, as well as basic results for random walks on Galton Watson trees and random graphs. He received the Rollo Davidson prize, the Loeve prize, and is an international member of the US National Academy of Sciences.