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.Allowed 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:
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:30-9:30 AM.
-
You can get the sensing matrix X and the measurement y using the following link:
https://drive.switch.ch/index.php/s/qXVYhYlCm4AYyrj
Please submit a single CSV file containing the matrix representing the image you recovered with your group name as the file name. The delimiter of the output CSV file should be ',' and each row of the matrix separated by a newline. The entries in the output CSV should be in {0,1,2}. Please adhere to this format.
-
-