Markov chains and algorithmic applications
Weekly outline
-
The course starts on Tuesday, September 9, 2023, at 8:15 AM in room BS 260.
Official course schedule:
- Lectures on Tuesday, 8:15-10:00 AM, in room BS 260.
Grading scheme: midterm 15%, mini-project 15%, final exam 70%
- Exercise sessions on Tuesday, 10:15-12:00 AM, in room BS 260.Final exam: date TBAAllowed material: two recto-verso handwritten A4 pages (but stylet+ipad is also fine)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:
TBA
References:
- 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
-
Cutoff phenomenon
-
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:30-9:30 AM.
