Schedule of Lectures
- 8/25:
-
Lecture: Recurrence vs. transience of random walks.
“Brute-force” proof of recurrence for random walks in
the 1D and 2D grid.
-
Reading: None.
-
Scribe notes by Brad Gulko, in preparation.
- 8/30 and 9/1: Class canceled.
- 9/6:
-
Lecture: “Brute-force” proof of transience for random walk in the 3D grid. Proofs of recurrence vs. transience for grids via spectral analysis of torus graphs.
-
Reading: None.
-
Scribe notes by Bruno Abrahao.
- 9/8: Class canceled due to flooding.
- 9/13:
- 9/15:
-
Lecture: Rayleigh monotonicity. Electrical flows in infinite graphs and their relation to recurrence vs. transience. Proof of recurrence for 2D grid using electrical networks.
-
Reading: Doyle and Snell, Chapter 2.
-
Scribe notes by Anna Blasiak, in preparation.
- 9/20:
-
Lecture: Proof of transience for 3D grid using electrical networks. Effective resistance, commute time, and cover time. Kirchhoff's matrix-tree theorem.
-
Reading: Doyle and Snell, Chapter 2.
-
Scribe notes by Pramook Khungurn, in preparation.
- 9/22:
-
Lecture: The matrix-tree theorem and effective resistances. Wilson's algorithm for sampling spanning trees.
-
Reading: Lyons and Peres, Chapter 4.1.
- 9/27:
- 9/29:
- 10/4: