Discrete Probability:
        Random Walks, Random Graphs and Percolation

                                            Winter semester 2018/19

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). Other moduls upon request.

Lecturer: Markus Heydenreich

Content: We are discussing four different aspects of discrete probability, in the following order. A slight emphasis is put on the third subject.

1. Markov chains on finite graphs, mixing time and cutoff phenomena
2. Random walk and electrical networks
3. Percolation
   
4. 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. Follow up by a seminar during summer term 2019.

Lecture: Monday and Wednesday 10-12 in room A027 (Math. Institute).

Date	Material covered	References
15 Oct	Introduction, definition	[LPW] 1.1, 1.3
17 Oct	Stationary distributions	[LPW] 1.5
22 Oct	TV distance, convergence theorem	[LPW] 4.1, 4.3
24 Oct	Relaxation time, TV distance via coupling	[LPW] 12.2, 4.2
29 Oct	Mixing times for special Markov chains	[KP] Thm 1.4, 1.5 [LPW] 8.2
31 Oct	No lecture! (Extra lecture Nov 29.)
5 Nov	MCMC	[Häg] 3,9 [LPW] 3.3.5
7 Nov	Coupling from the past	[Häg] 10
12 Nov	Electrical networks	[Gri] 1.2, 1.3
14 Nov	Recurrence and Transience via electr. Networks	[Gri] 1.4
19 Nov	Pólya's theorem	[Gri] 1.5
21 Nov	Percolation: Introduction	[DC] 1
26 Nov	Correlation inequalities	[DC] 2.1-2.3
28 Nov	Percolation toolbox	[DC] 2.3, 2.4
29 Nov	Guest lecture by Geoffrey Grimmett: Uniqueness of the infinite cluster	[Gri] 5.2
3 Dec	Sharp phase transition I	[DC] 3.1, [HH] 3.2
5 Dec	Sharp phase transition II	[HH] 3.3-3.7
10 Dec	pc=1/2 in 2D, RSW theory	[Gri] 5.6, 5.5
12 Dec	RSW (cont.), correlation length	[Gri] 5.5
17 Dec	Cardy's formula	[Gri] 5.7
19 Dec	Cardy's formula (cont.), Crit. exponents	[Gri] 5.7, 5.4
7 Jan	Percolation in high dimension: Introduction	[Gri] 5.4, [HH] Chap. 4
9 Jan	Lace Expansion	[HH] Chapter 6
14 Jan	Bounds on lace expansion coefficients	[HH] Chapter 7
16 Jan	Lace expansion continued	[HH] Chapter 7/8
21 Jan	Completing the lace expansion argument	[HH] Chapter 8, [Hof] 3.3
23 Jan	Erdös-Renyi random graphs	[Hof] 4.1, 4.2
28 Jan	ER-Graphs: Subcritical regime	[Hof] 4.3
30 Jan	ER-Graphs: Supercritical regime	[Hof] 4.4
4 Feb	ER-Graphs: Supercritical case (ctd.), Critical case	[Hof] 4.4
6 Feb	Critical ER-Graphs	[Hof] 5.1

Exercise: Monday 12:30-14:00 in room B 041 (Math. Institute).

• Exercises from 21 Oct
• Exercises from 28 Oct
• Exercises from 5 Nov
• Exercises from 12 Nov
• Exercises from 19 Nov
• Exercises from 26 Nov
• Exercises from 3 Dec
• Exercises from 10 Dec
• Exercises from 17 Dec
• Exercises from 7 Jan
• Exercises from 14 Jan

• Exercises from 21 Jan
• Exercises from 28 Jan
• Exercises from 4 Feb
  

Exam: Oral examination on Friday, 22 February 2019 (past).

Second examination (oral as well) on Wednesday, 17 April 2019.
In order to register for the second exam, please send an email to Nannan Hao MSc via Nannan.Hao@math.lmu.de and communicate the following:

• Full name
• Studiengang
• Student number
• Preference for morning/afternoon (if desired)
• Which module should we book the exam (if known)
  

References:

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

Note: During the winter semester, our group offers two courses on the master level, Stochastic Processes (SP) and Discrete Probability (DP). 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 the a thesis in probability theory. DP is of slightly different character, it presents a kaleidoscope of very specialized topics in an research area that is characterized by breathtaking development during recent years.