Markov chains and algorithmic applications

Official course schedule:

- Lectures on Tuesday, 8:15-10:00 AM, in room BS 260.
- 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.ch

Teaching 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, 2017

Final exam date and place:

Saturday, January 24, 9h15-12h15, in room CO 1

Allowed material: two recto-verso handwritten A4 pages (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).

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)

Sampling:

• Introduction, importance and rejection sampling
• Metropolis-Hastings algorithm (MCMC sampling)
  

• Application: function minimization
• Simulated annealing
  

• Application: coloring problem
  
• Convergence analysis
  

Ising model:

• Introduction (Hamiltonian, Gibbs measure, various particular cases)
• MCMC sampling and Gibbs sampling
  
• Exact simulation

• Random mapping representation
• Forward and backward coupling
• Propp-Wilson theorem
• Monotone coupling

Mini-project competition on Tuesday, December 19, 8:15-9:30 AM.

Project Deadline: Sunday, December 15, at 23:55.

Details on the project competition

Once the competition has started, you will have access to a MATLAB file observations.mat on Moodle. This file contains the variables Y, W, m, n, whose names correspond to the ones given in the project description. You will have to load this file and run your simulated annealing algorithm on these observations. Finally you will save your estimate of X in a MATLAB file <your_team_name>.mat and submit it on Moodle.

• Instruction for MATLAB users
  

You can load the observations with load('observations.mat'). To save your estimate x_estimate use the instruction save('<your_team_name>','x_estimate'). Please make sure the variable name of your answer is x_estimate!

• Instruction for Python users
  

The Python script load_observations_matlab.py shows you how to load MATLAB file observations.mat with Python, and how to save your answer. Please make sure you save your estimate x_hat (or whatever its name) with the variable name x_estimate! You can do that with a dictionary {'x_estimate':x_hat} as the parameter mdict given to the function scipy.io.savemat (see the last line in the script).

• Given example