Course: Markov chains and algorithmic applications

Weekly outline

General
The course starts on Thursday, September 23, 2021, at 12:15 PM in room INM 202. Please note that video lectures of the entire course are available on SWITCHTube, but the course will be this year in presence in class. It is highly recommended that you are present in class.

Official course schedule:
- Lectures on Thursday // 12:15-2:00 PM // room INM 202
- 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
Alireza Modirshanechi // LCN // alireza.modirshanechi#epfl.ch
Xiangcheng Cao // IC master student // xiangcheng.cao#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
This week
Week 1 (September 23-24)
General introduction, Markov chains, classification of states, periodicity
Week 2 (September 30 - October 1)
Recurrence, transience, positive/null-recurrence
- Lecture 2 slides File
- lecture_notes2.pdf File
Week 3 (October 7-8)
Stationary and limiting distribution, two theorems
- Lecture 3 slides File
- lecture_notes3.pdf File
Week 4 (October 14-15)
Proof of the ergodic theorem, coupling argument
- Lecture 4 slides File
- lecture_notes4.pdf File
Week 5 (October 21-22)
Detailed balance, rate of convergence, spectral gap, mixing time
- Lecture 5 slides File
- lecture_notes5.pdf File
Week 6 (October 28-29)
Rate of convergence: proofs
- Lecture 6 slides File
- lecture_notes6.pdf File
Week 7 (November 4-5)
Cutoff phenomenon
- Lecture 7 slides File
- lecture_notes7.pdf File
Week 8 (November 11-12)
Sampling: introduction, examples of high dimensional distributions, and the Metropolis-Hastings algorithm
The midterm will take place on Friday, November 12, 3:15-5:15 PM.
- lecture 8 slides File
- lecture_notes8.pdf File
Week 9 (November 18-19)
Function minimization, simulated annealing, introduction to the coloring problem
- lecture 9 slides File
- lectures_notes9_10.pdf File
Week 10 (November 25-26)
Analysis of the coloring problem
- lecture 10 slides File
- lectures_notes9_10.pdf File
Week 11 (December 2-3)
Ising model, Glauber dynamics for the Ising model, general heat bath dynamics
- lecture 11 slides File
- lecture_notes11.pdf File
Week 12 (December 9-10)
Exact simulation: coupling from the past
- lecture 12 slides File
- lecture_notes12_13.pdf File
Week 13 (December 16-17)
Exact simulation: proof of Propp-Wilson theorem
Monotone coupling and application to the Ising model
- lecture 13 slides File
- lecture_notes12_13.pdf File
Week 14 (December 23)
Mini-project competition on Thursday, December 23, 12:15-2:00 PM.