Markov chains and algorithmic applications
Aperçu des semaines
-
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.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 assistant:
Anastasia Remizova // SMILS // INR 140 // 021 693 61 70 // anastasia.remizova#epfl.ch
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, 2017Final exam date and place:
Saturday, January 24, 9h15-12h15, in room CO 1
-
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 / card shuffling (time permitting)
-
Midterm exam on Tuesday, 8:15-10:15 AM, in rooms BS 260 (letters A to K) and CO 1 (letters L to Z). [Attention: ROOM CHANGE!]Content: everything seen until week 7 (included).Allowed material: one recto-verso handwritten A4 page (but stylet+ipad is also fine). Apart from that, this is a closed book exam. No electronic device allowed, except a simple calculator (of the type TI-30 eco RS or similar).
-
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.
