Markov chains and algorithmic applications
Aperçu des semaines
-
The course starts on Thursday, September 22, 2022, at 12:15 PM in room INM 202. 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 INM 202
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%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 Dashade // SACS // akash.dashade#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 (bis): card shuffling
- Sampling: introduction
-
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 23, 12:15-2:00 PM.