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 (from Nov 10: Zoom link for the course).

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%

Exam date: Monday, January 23, 2023, 3:15-6:15 PM, room CM 1 121

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
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
The midterm will take place on Friday, November 4, from 3:15 PM until 5:15 PM, in room INM 202.
Allowed material: one handwritten double-sided A4 page.
Exam content: everything until week 6.
Week 8 (November 10-11)
- Cutoff phenomenon (bis): card shuffling
- Sampling: introduction
  
  NB: No exercises this week!
- Lecture 8 slides File
- lecture_notes8.pdf File
Week 9 (November 17-18)
Sampling: importance and rejection sampling, Metropolis-Hastings algorithm
Week 10 (November 24-25)
- Application: function minimization
- Simulated annealing
Week 11 (December 1-2)
- Application: coloring problem
- Convergence analysis
- Lecture 11 slides File
- lecture_notes11.pdf File
This week
Week 12 (December 8-9)
- Ising Model and Metropolis-Hastings algorithm
- Glauber dynamics (Gibbs sampling)
- lecture_notes12.pdf File
Week 13 (December 15-16)
- Exact simulation (coupling from the past): Propp-Wilson theorem
- Monotone coupling and application to the Ising model
- Homework 13 File
- lecture_notes13.pdf File
Week 14 (December 22)
Mini-project competition on Thursday, December 22, 12:15-2:00 PM.
Course mini-project (2022-2023)
- Project description File