Department Mathematik



                          Advanced Discrete Probability
        Random Walks, Random Graphs and Percolation

                                            Winter semester 2020/21

This is a course for master students in Mathematics, TMP and Finance- and Insurance Mathematics. The course is egligible as Special topics in Stochastics as module WP 32 (for Math), as well as WP 43 and 44 (for TMP), resp. WP 10 (FIM, PO 2011) and WP 13 (FIM, PO 2019). Other moduls upon request.

LecturerMarkus Heydenreich

Content: We discuss a number of special topics in the theory of discrete random structures. The lecture covers both classical as well as very recent developments. The course is structures into five themes:

  1. Markov chains on finite graphs, mixing time and cutoff phenomena
  2. Random walk and electrical networks
  3. Self-avoiding walk
  4. Percolation
  5. Erdös-Renyi random graphs
There is no written syllabus, but I give references to all topics discussed during the lecture.
The aim of the course is to make students acquainted with current research topics in this area. Ideal starting point for a master thesis in this area.

Lecture: Monday and Thursday 12-14. Mostly online via Zoom.

Exercise: Online via Zoom (working on problem sheets in small groups), every Wednesday 10-12.

Registration: Sign up for this course via MOODLE, please. The passphrase is: RandomCourse
All further communication is solely provided via moodle.

Exam: We plan an oral exam (via Zoom).

  • [LPW] L. Levin, Y. Peres, E. Wilmers: Markov chains and mixing times. Second edition. AMS 2018.  [pdf of first edition]
  • [Gri] G. Grimmett: Probability on graphs. Second edition. Cambridge University Press 2018. [pdf]
  • [LP] R. Lyons, Y. Peres: Probability on graphs and networks. Cambridge University Press 2016. [book page]
  • [DC] H. Duminil-Copin: Introduction to percolation theory. Lecture notes 2017. [pdf]
  • [HH] M. Heydenreich, R. van der Hofstad: Progress in high-dimensional percolation and random graphs. Springer 2017. [pdf of preprint]
  • [Hof] R. van der Hofstad: Random graphs and complex networks. Cambridge University Press 2017. [pdf]
  • [Gri99] G. Grimmett: Percolation. Second Edition. Springer 1999.
  • [KP] J. Komjathy and Y. Peres: Topics in Markov chains: Mixing and escape rate.
    Proceedings of Symposia in Pure Mathematics, Volume 91. AMS 2016. [arXiv]
  • [Häg] O. Häggström: Finite Markov Chains and Algorithmic Applicatons, LMS Student Texts 52, Cambridge University Press 2002.
Specific references to the literature are provided during the course.

Note: During the winter semester, our group offers two courses on the master level, Stochastic Processes (SP) and Advanced Discrete Probability (ADP). Both courses are fairly independent and focus on different aspects. SP is a core module in probability theory, where many fundamental concepts are introduced, and it is therefore strongly advised to all students who plan to write a thesis in probability theory. ADP is of slightly different character, it presents a kaleidoscope of very specialized topics in a research area that is characterized by breathtaking development during recent years.