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:1510:00 AM, in room BC 01.
Grading scheme: midterm 20%, miniproject 20%, final exam 60%
 Exercise sessions on Tuesday, 10:1512:00 AM, in room INF 213.Final exam on Monday, January 29, 9h1512h15, in rooms CM 1120, CM 1121.Allowed material: two rectoverso 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 (20202021 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/nullrecurrence

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:0010:00 AM, room CE 1515Allowed material: one rectoverso handwritten A4 page (but stylet+ipad is also fine)

Sampling:
 Introduction, importance and rejection sampling
 MetropolisHastings 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
 ProppWilson theorem
 Monotone coupling

Ising model:
 Introduction (Hamiltonian, Gibbs measure, various particular cases)
 MCMC sampling and Gibbs sampling
 Exact simulation

Miniproject competition on Tuesday, December 19, 8:309: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.

