Markov chains and algorithmic applications
Weekly outline
-
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
Grading scheme: midterm 20%
- Exercise sessions on Friday // 3:15-5:00 PM // room INM 202
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 121Allowed material: two handwritten double-sided A4 pagesQ&A session: Friday, January 20, 2023, 10-12 AM, room INR 113Course 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.chReferences:
- 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 -
General introduction, Markov chains, classification of states, periodicity
-
Recurrence, transience, positive/null-recurrence
-
Stationary and limiting distribution, two theorems
-
Proof of the ergodic theorem, coupling argument
-
Detailed balance, rate of convergence, spectral gap, mixing time
-
Rate of convergence: proofs
-
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.
-
- Cutoff phenomenon (bis): card shuffling
- Sampling: introduction
NB: No exercises this week!
-
Sampling: importance and rejection sampling, Metropolis-Hastings algorithm
-
- Application: function minimization
- Simulated annealing
-
- Application: coloring problem
- Convergence analysis
- Application: coloring problem
-
- Ising Model and Metropolis-Hastings algorithm
- Glauber dynamics (Gibbs sampling)
-
- Exact simulation (coupling from the past): Propp-Wilson theorem
- Monotone coupling and application to the Ising model
-
Mini-project competition on Thursday, December 22, 12:15-2:00 PM.
