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

**Solutions can be submitted on paper or electronically. I recommend pdf compiled from latex.**

** Last modified Dec 5, 2017.
**