Opening Spectral Graph Theory: The Standard Random Walk
Spectral Graph Theory: The Standard Random Walk
- Length
- 25 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Invariant distribution of a random walk
The standard random walk on an undirected graph steps from each vertex to a uniformly random neighbor. O'Donnell shows that on an irregular graph, choosing the start vertex with probability gives a distribution the walk preserves at every step. He states that on connected, non-bipartite graphs this invariant distribution is the limit as the walk length grows, with disconnected and bipartite graphs as counterexamples. The last part links mixing speed to graph cuts and the quadratic form over edges. Basic graph theory and elementary probability are assumed. The material forms lecture 13b of O'Donnell's CMU course A Theorist's Toolkit (15-750), with Spielman's Spectral and Algebraic Graph Theory as a reference.

Your comment is kept while you sign up.Sign in
Shows that starting a random walk at a vertex with probability leaves the distribution fixed at every step.
The standard random walk on an undirected graph steps from each vertex to a uniformly random neighbor. O'Donnell shows that on an irregular graph, choosing the start vertex with probability π(v) = deg(v)/2m gives a distribution the walk preserves at every step. He states that on connected, non-bipartite graphs this invariant distribution is the limit as the walk length grows, with disconnected and bipartite graphs as counterexamples. The last part links mixing speed to graph cuts and the quadratic form over edges. Basic graph theory and elementary probability are assumed. The material forms lecture 13b of O'Donnell's CMU course A Theorist's Toolkit (15-750), with Spielman's Spectral and Algebraic Graph Theory as a reference.
This lecture
Lecture 40 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.