Opening Spectral Graph Theory III: Mixing Time
Spectral Graph Theory III: Mixing Time
- Length
- 39 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 6: Before the lecture
The mixing time of a random walk on a graph is controlled by the eigenvalues of its transition operator. Starting from the spectral gap, O'Donnell shows how a bipartite graph's eigenvalue of makes the walk oscillate forever, and how a lazy walk removes it. Distance to the stationary distribution is measured by chi-squared divergence, the variance of the density ratio from one. Expanding that ratio in the eigenvector basis shows each step shrinks the variance, so the distance decays exponentially in the gap and the step count. Part of CMU 15-750: A Theorist's Toolkit at Carnegie Mellon University, the session takes questions on disconnected graphs and cycles, and assumes Laplacians.
Your comment is kept while you sign up.Sign in
Proves that chi-squared distance to stationarity decays exponentially in the spectral gap of a lazy walk.
The mixing time of a random walk on a graph is controlled by the eigenvalues of its transition operator. Starting from the spectral gap, O'Donnell shows how a bipartite graph's eigenvalue of makes the walk oscillate forever, and how a lazy walk removes it. Distance to the stationary distribution is measured by chi-squared divergence, the variance of the density ratio from one. Expanding that ratio in the eigenvector basis shows each step shrinks the variance, so the distance decays exponentially in the gap and the step count. Part of CMU 15-750: A Theorist's Toolkit at Carnegie Mellon University, the session takes questions on disconnected graphs and cycles, and assumes Laplacians.
This lecture
Lecture 47 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.