After successful completion of the course, students are able to...

...describe and analyze random walks on graphs

...describe the relationship between the geometry of the graph and the long term behavior of the random walk, in particular

...characterize recurrence and transience in terms of the electrical properties of the graph

...investigate questions of convergence towards the stationary distribution (mixing times, spectral gap) for finite-state Markov chains

Random walks and electric networks

• Discrete Dirichlet form, energy, effective resistances/conductances
• Characterization of the asymptotic behavior via the network resistance
• Gaussian Free Field on a graph
• Loop-erased random walk
• Uniform random spanning tree of a graph: Wilson’s algorithm and determinantal correlations (Burton-Pemantle theorem)

Random walks on finite graphs: speed of convergence

• Mixing time T mix (reversible and non-reversible random walks)
• T mix upper bounds: path coupling and weighted distances
• Spectral gap, variational principle and time correlations
• Bounding the spectral gap: geometric comparison methods
• The cutoff phenomenon

Lecture and homework problems

Exam

Basics of probability theory and stochastic processes, Markov Chain, Gaussian processes