Course: Markov chains and algorithmic applications

Weekly outline

General

The course starts on Thursday, September 22, 2022, at 12:15 PM in room CM 5. Please note that video lectures of the entire course are available on SWITCHTube, but please note that it is highly recommended that you are present in class.

Official course schedule:

- Lectures on Thursday // 12:15-2:00 PM // room CM 5
- Exercise sessions on Friday // 3:15-5:00 PM // room INM 202
Grading scheme: midterm 20%
mini-project 20% (+5% for the winning team)

final exam 60%

Course instructors:

Nicolas Macris // LTHC // INR 134 // 021 693 81 14 // nicolas.macris#epfl.ch (first part of the course)
Olivier Lévêque // LTHI // INR 132 // 021 693 81 12 // olivier.leveque#epfl.ch (second part of the course)

Teaching assistants:

Farzad Pourkamaili // LTHC // farzad.pourkamali#epfl.ch
Pierre Quinton // LTHI // pierre.quinton#epfl.ch
Akash Dhasade // SACS // akash.dhasade#epfl.ch

References:

- SWITCHTube channel of the course (2020-2021 lectures)
- Geoffrey R. Grimmett, David R. Stirzaker, Probability and Random Processes, 3rd edition, Oxford University Press, 2001
- D. Levin, Y. Peres, E. Wilmer, Lecture Notes on Markov Chains and Mixing Times, 2nd edition, AMS, 2017
Week 1 (September 22-23)
General introduction, Markov chains, classification of states, periodicity
This week
Week 2 (September 29-30)
Recurrence, transience, positive/null-recurrence
Week 3 (October 6-7)
Stationary and limiting distribution, two theorems
Week 4 (October 13-14)
Proof of the ergodic theorem, coupling argument
Week 5 (October 20-21)
Detailed balance, rate of convergence, spectral gap, mixing time
Week 6 (October 27-28)
Rate of convergence: proofs
Week 7 (November 3-4)
Cutoff phenomenon
Week 8 (November 10-11)
- Cutoff phenomenon (bis): card shuffling
- Sampling: introduction
- lecture_notes8.pdf File
Week 9 (November 17-18)
Sampling: Metropolis-Hastings algorithm
- lectures_notes9.pdf File
- Homework 9 File
Week 10 (November 24-25)
- Application: function minimization
- Simulated annealing
- lectures_notes10.pdf File
- Homework 10 File
Week 11 (December 1-2)
- Application: coloring problem
- Convergence analysis
- lecture_notes11.pdf File
- Homework 11 File
Week 12 (December 8-9)
- Ising Model and Metropolis-Hastings algorithm
- Glauber dynamics (Gibbs sampling)
- lecture_notes12.pdf (TO BE EDITED) File
- Homework 12 File
Week 13 (December 15-16)
- Exact simulation (coupling from the past): Propp-Wilson theorem
- Monotone coupling and application to the Ising model
- lecture_notes13.pdf File
- Homework 13 File
Week 14 (December 22)
Mini-project competition on Thursday, December 23, 12:15-2:00 PM.