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
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
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
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
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
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.