• 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.