- Location: 1-820, time: Friday 14:00-15:30
Topic of this semester: Random walks on graphs
Lecture notes randwalk4.pdf (Remark: may change as lectures progress!)
Homework No. 1: Exercises 1.12, 2.27, 2.33, 2.34, 2.36 in the lecture notes.
Due: Monday, Oct 16.
Homework No. 2: Exercises 2.30, 2.37, 3.16, 3.17, 3.18 in the lecture notes.
Due: Monday, Nov 13.
Homework No. 3: Exercises 4.12, 4.13, 4.14, 4.15, 4.17 in the lecture notes.
Due: Tuesday, Dec 12.
Solutions can be submitted on paper or electronically.
I recommend pdf compiled from latex.
Weakly topics:September 15
Random walk on a finite connected graph. With probability 1, every node is visited infinitely often. Harmonic functions: existence and uniqueness.September 22.
Stationary distribution. Spectral decomposition of the transition matrix. On a nonbipartite graph, the distribution after n steps tends to the stationary distribution. Return time.September 29.
Hitting time: examples (paths, cycles, trees). Rubber band model. The maximum order of hitting times is n^3. Linear algebraic formula for hitting times. Random Target Lemma.October 6.
Hitting time: Cycle Reversal Lemma. Commute time: Connection with effective resistance in electrical networks. Cover time: estimates by number of nodes edges, and by minimal and maximal hitting time. Application: universal traverse sequences.October 13.
Mixing time. Variational distance. Lazy walk. Bounding the mixing time by the eigenvalue gap. Example: k-cube.October 20.
Coupling. Bounding the mixing time by the coupling time. Simple examples: cube, path. Mixing time of the random walk on k-colorations.October 27.
Conductance of a graph. Bounding the eigenvalue gap in terms of conductance.November 17.
Conductance and packing of paths. Applications: cube, node- and edge-transitive graphs. Stopping rules: examples, naive rule, basic equation and consequences.November 24.
Stopping rules: optimal rules, characterization via halting states. Formula for the mixing time. Mixing and epsilon-mixing.December 1.
Volume computation. How is a convex body given? Lower bound on the error of polynomially computable estimates. Multi-stage Monte-Carlo algorithm: outline.