Ravi Montenegro's Research Information

Other Pages
My Home Page
UML Math
GATech Math
Yale Math

Math 8843 - Convergence of Markov Chains

These are notes for a graduate course on Convergence of Markov chains I taught in Fall 2004 at Georgia Tech. The previous term Dana Randall taught a related undergraduate course, so in this class we focused on theory and advanced methods. Lectures 8-21 covers material on Log-Sobolev, Nash Inequalities, and Evolving Sets; this is better learnt from my book with Prasad Tetali (PDF available on my research page) in which we develop more elegant arguments than what was available at the time of this course.

Related Courses and Notes

Lectures: (subject to change as the term progresses)
  • Introduction
    • AS1 and AS2: Markov chain basics. (Thm 2.1 in EV2 contains a proof of Fundamental Theorem)
    • Lecture 4: Variation distance and mixing time.
  • Analytic methods of bounding mixing time
    • Lecture 5: L_p distances and the spectral decomposition.
    • Lecture 6: Mixing time of the simple random walk on a cycle.
    • Lecture 7: Exponential decay and lower bounding mixing time.
    • Lecture 8: Dirichlet forms and comparison of spectral gap.
    • Lecture 9: Canonical paths.
    • Lectures 10 and 11 were a preview of geometric methods (see below).
    • Lecture 12: Continuous time chains and modified log-Sobolev.
    • Lecture 13: Operator norms and Nash inequalities.
    • Lecture 14: log-Sobolev, tensorization.
      • Homework 1 is now available and is due Monday Oct 4 (in two weeks).
    • Lecture 15: (9/20) Decomposition and some examples.
  • Geometric methods of bounding mixing time
    • Lecture 10: Conductance and the spectral gap.
    • Sam and Teena taught approximating the permanent (Thanks!).
    • Lecture 11 / Combinatorics Seminar: Evolving set and Cheeger bounds on the top and bottom eigenvalues.
    • Lectures 12-15 were on analytic topics (see above).
    • Lecture 16: Evolving sets and distances.
    • Lecture 17: Mixing times and conductance.
    • Lecture 18: Simple random walk on a cycle, new Cheeger Inequality.
    • Lecture 19: Consequences of new Cheeger, Average congestion.
    • Lecture 20: Average Conductance, the Easy Inequality Prover.
    • Lecture 21: Vertex congestion and comparison theorems
  • Volume and Integration of log-concave functions
    (I have not edited these notes, so they are not recommended for use outside my class.)
    • Note-takers: Please try to type of notes within a few days of class, so that the rest of the class has them available soon. Those who are typing notes can use the Lecture 17 notes as a template, along with the Bibtex reference list. To use this type "latex lecture17.tex", then "bibtex lecture17", then "latex lecture17.tex" twice.
    • Lecture 22: Reduction of volume estimation to uniform sampling.
    • Lecture 23: Introduction to the Ball Walk.
    • Lecture 24: Local Conductance and uniform sampling.
    • Lecture 25: Mixing time of Ball Walk, Localization Lemma.
    • The proofs for the next three lectures are based on this paper on "Blocking Conductance".
    • Lecture 26: Bounding Conductance I
    • Lecture 27: Bounding Conductance II
    • Lecture 28: Bounding Conductance III
      • Start thinking about your presentation.
  • Walks on groups, Cayley graphs and other highly symmetric objects
    • Lecture 29-31: Symmetry Analysis of Reversible Markov Chains (see the paper here). There are numerous minor mistakes in the paper so don't be too surprised if something doesn't seem right.)
    • Lecture 32-34: Strong Uniform Stopping Times and applications
    • Lecture 35: Analysis of Riffle Shuffle
    • Lecture 36: Analysis of Riffle Shuffle II
      (based largely on Aldous and Diaconis which is accessible online via the GATech library electronic journals, see also Diaconis' survey on shuffling for the latest developments)
    • (see Igor Pak lectures 11-13 for intro to strong uniform stopping times)
      • For more information on walks on groups see:
        • Igor Pak's random walk papers. His early papers do a lot on strong uniform stopping times. His Ph.D. Dissertation "Random Walks on Groups : Strong Uniform Time Approach" is probably the best place to find what can be done with Strong Uniform Times.
        • Laurent Saloff-Coste has many papers on random walks on groups, see in particular "Random walks on finite groups".
        • Martin Hildebrand has some stuff related to walks on groups, although not immediately related to what we looked at.
        • Persi Diaconis is responsible for much of the study of random walks on groups. His book "Group Representations in Probability and Statistics" is a good source, but is out of print.
  • Generalized knapsack and applications
  • Student presentations
    • Week 13 (11/15):
    • Week 14 (11/22):
    • Week 15 (11/29):