Markov Chain Mixing

Time:15:20 - 16:55, Wed,Fri, 10/12/2022 - 1/6/2023

Venue:Venue: 1129B Zoom: 482 240 1589 PW: BIMSA

Speaker:Yuval Peres (Research Fellow)

Record: Yes

Level: Graduate

Language: English


Undergraduate Probability and Linear Algebra, some measure theoretic probability: Conditional expectation, Laws of large numbers. The first chapter of Durrett’s graduate text or taking  the course “Probability 1” given by Prof. Hao Wu at Tsinghua will provide ample background. That course can be taken in parallel with this course.

The textbook for the course is “Markov chains and mixing times”, second edition, PDF is available from

In the last part of the course, we will see new material that is not in that book, and explore open problems and directions of current research.


Background: The modern theory of Markov chain mixing is the result of the convergence, in the 1980's and 1990's, of several threads:

For statistical physicists, Markov chains become useful in Monte Carlo simulation  The mixing time determines the running time for simulation.  Deep connections were found between rapid mixing and spatial properties of spin systems. In theoretical computer science, Markov chains play a key role in sampling and approximate counting algorithms.

At the same time, mathematicians were intensively studying random walks on groups. Both spectral methods and probabilistic techniques, such as coupling, played important roles. Ingenious constructions of expander graphs (on which random walks mix especially fast) were found. The connection  between eigenvalues and expansion properties was first discovered in differential geometry, but then became central to the study of Markov chain mixing.


However, In the second part of the course we will see new material that is not in that book, and explore open problems and directions of current research.


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 and Time Reversals  

1.7. Gambler's Ruin  

1.8. Coupon Collecting  

1.9  The cycle and the Hypercube  

1.10 The Polya Urn Model  

Week 2: Mixing, coupling and stationary times

2.1. Total Variation Distance and coupling

2.2. The Convergence Theorem

2.3. Mixing in total variation

2.4. Uniform mixing and mixing in other norms  

2.5. Grand Couplings  

2.6. Top-to-Random Shuffle

2.7. Stationary Times  

2.8. Strong Stationary Times and separation distance  

2.9. Stationary Times and Cesaro Mixing Time  

2.10. Optimal strong stationary times

Week 3:  Lower Bounds and the symmetric group

3.1. Counting and Diameter Bounds  

3.2. Bottleneck Ratio  

3.3. Distinguishing Statistics  

3.4. The Symmetric Group  

3.5. Random Transpositions and adjacent transpositions

3.6. Riffle shuffles

Week 4: Random Walks, electrical networks and hitting times

4.1. Networks and Reversible Markov Chains  

4.2. Harmonic Functions  

4.3. Voltages and Current Flows  

4.4. Computing effective resistance

4.5. Random Target Times  

4.6. Commute Time  

4.7. Hitting Times on Trees  

4.8. Hitting Times for Eulerian Graphs  

4.9. Hitting Times for the Torus  

Week 5: From hitting times to Cover Times

5.1. Bounding Mixing Times via Hitting Times  

5.2. The Matthews Method  

5.3. Spanning Tree Bound for Cover Time  

5.4. The Gaussian Free field

Week 6: Eigenvalues  

6.1. The Spectral Representation of a Reversible Transition Matrix  

6.2. The Relaxation Time  

6.3. Eigenvalues and Eigenfunctions of Some Simple Random Walks  

6.4. Spectral Formula for the Target Time  

6.5. Time Averages approximate space averages: MCMC  

6.6. Bounds on Spectral Gap via Contractions  

Week 7: Expansion of graphs and networks

7.1. The Dirichlet Form and the Bottleneck Ratio  

7.2. Comparison of Markov Chains  

7.3. Expander Graphs  

Week 8: The Transportation Metric and Path Coupling  

8.1. Path Coupling  

8.2. Rapid Mixing for Colorings  

8.3. Approximate Counting  

8.4. Curvature of Markov chains

Week 9: Simulation and perfect sampling

9.1. Monte Carlo sampling

9.2. unbiasing random bits

9.3. Glauber and Metropolis dynamics

9.4. Coupling from the past

9.5. sampling uniform spanning trees

Week 10: The Ising Model  

10.1. Fast Mixing at High Temperature  

10.2. The Complete Graph  

10.3. The Cycle  

10.4. The Tree  

10.5. Block Dynamics  

10.6. Lower Bound for Ising on Square  

Week 11: The Cutoff Phenomenon  and continuous time chains

11.1. The hypercube versus the cycle

11.2. The product condition and the Aldous-Pak examples

11.3. Equivalence of continuous time chains and lazy chains.

11.4. birth-death chains and cutoff on trees

11.5. Ramanujan graphs

Week 12:  Research directions

12.1. Universal lower bound for Ising, open for Potts

12.2. Swendsen -Wang Dynamics: the exponent quarter conjecture

12.3. Monotone subsets of the cube: The Ding-Mossel Theorem

12.4. Random walks on invertible matrices modulo 2

12.5. Random walk on percolation clusters and dynamical percolation

Lecturer Intro

Yuval Peres obtained his PhD  in 1990 from the Hebrew University, Jerusalem. He was a postdoctoral fellow at Stanford and Yale, and  was then a Professor of Mathematics and Statistics in Jerusalem and in Berkeley. Later, he was a Principal researcher at Microsoft. Yuval has published more than 350 papers in most areas of probability theory, including random walks, Brownian motion, percolation, and random graphs. He has co-authored  books on Markov chains, probability on graphs, game theory and Brownian motion, which can be found at . His presentations are available at  Dr. Peres is a recipient of the Rollo Davidson prize and the Loeve prize. He has mentored 21 PhD students including Elchanan Mossel (MIT, AMS fellow),  Jian Ding (PKU, ICCM gold medal and Rollo Davidson prize),  Balint Virag and Gabor Pete (Rollo Davidson prize).

Dr. Peres was an invited speaker at the 2002 International Congress of Mathematicians in Beijing, at the 2008 European congress of Math,  and at the 2017 Math Congress of the Americas. In 2016, he was elected to the US National Academy of Science.

Lecturer Email:

TA: Dr. Andrew Best,

DATESeptember 6, 2022
Related News
    • 0

      Introduction to Exceptional Geometry

      Record: YesLevel: GraduateLanguage: EnglishPrerequisiteLinear algebra, basics of Riemmanian geometryAbstractThe classification of Riemannian manifolds with special holonomy contains two “exceptional” cases: G2 and Spin(7). Manifolds with holonomy contained in G2 or Spin(7) are called G2-manifolds or Spin(7)-manifolds, respectively. In this course, I will introduce various topics of G2 and Spi...

    • 1

      Algebraic Morava K-theory

      RecordYesAbstractThis mini-course focuses on Quillen's approach to cobordism theories and the adaptation of these ideas in the context of algebraic geometry. We will discuss how formal group laws are related to generalized cohomology theories, stack of formal groups and Morava K-theories.ReferenceD. Quillen, "Elementary proofs of some results of cobordism theory using Steenrod operations", Adva...