Markov chains and algorithmic applications
Weekly outline
-
The course starts on Tuesday, September 19, 2023, at 8:15 AM in room BC 01.
Official course schedule:
- Lectures on Tuesday, 8:15-10:00 AM, in room BC 01.
Grading scheme: midterm 20%, mini-project 20%, final exam 60%
- Exercise sessions on Tuesday, 10:15-12:00 AM, in room INF 213.Final exam on Monday, January 29, 9h15-12h15, in rooms CM 1120, CM 1121.Course instructors:
Olivier Lévêque // LTHI // INR 132 // 021 693 81 12 // olivier.leveque#epfl.ch
Nicolas Macris // SMILS // INR 134 // 021 693 81 14 // nicolas.macris#epfl.chTeaching assistants:
Anand George // SMILS // anand.george#epfl.ch
Guanyu Zhang // IN master student // guanyu.zhang#epfl.chReferences:
- Mediaspace channel of the course (2020-2021 edition)
- 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
-
Midterm exam on Tuesday, 8:00-10:00 AM, room CE 1515Allowed material: one recto-verso handwritten A4 page (but stylet+ipad is also fine)
-
Sampling:
- Introduction, importance and rejection sampling
- Metropolis-Hastings algorithm (MCMC sampling)
-
- Application: function minimization
- Simulated annealing
-
- Application: coloring problem
- Convergence analysis
- Application: coloring problem
-
Exact simulation (coupling from the past):
- Random mapping representation
- Forward and backward coupling
- Propp-Wilson theorem
- Monotone coupling
-
Ising model:
- Introduction (Hamiltonian, Gibbs measure, various particular cases)
- MCMC sampling and Gibbs sampling
- Exact simulation
-
Mini-project competition on Tuesday, December 19, 8:15-10:00 AM.
