Markov chains and algorithmic applications
Weekly outline
-
The course starts on Thursday, September 19, 2019, at 12:15 PM in room INM 202.
Course schedule:
- Lectures on Thursday // 12:15-2:00 PM // room INM 202
- Exercise sessions on Friday // 3:15-5:00 PM // room INM 202
Grading scheme: midterm 20%
mini-project 20%exam 60%Midterm exam on Friday, November 8, 3:15-5:15 PM, room CE 1 6
Allowed material: two handwritten single-sided A4 pagesFinal exam on Thursday, January 30, 12:15-3:15 PM, room AAC 231
Allowed material: four handwritten single-sided A4 pagesCourse instructors: Olivier Lévêque // LTHI // INR 132 // 021 693 81 12 // olivier.leveque@epfl.ch (first part of the course)
Nicolas Macris // LTHC // INR 134 // 021 693 81 14 // nicolas.macris@epfl.ch (second part of the course)Teaching assistant: Alireza Modirshanechi // LCN // AAB 141 // 021 693 66 35 // alireza.modirshanechi@epfl.ch
References:
- 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 times
-
Rate of convergence: proofs
-
Reflection principle, arcsine law, cutoff phenomenon
-
Regular class on Thursday (not exam material): cutoff phenomenon (cont'd), card shuffling
Midterm exam on Friday, November 8, 3:15-5:15 PM, room CE 1 6
Allowed material: two handwritten single-sided A4 pages
-
Sampling: introduction and general methods, Metropolis-Hastings algorithm -
Applications: function minimization, coloring problem
-
Ising model, Glauber dynamics
-
End of Glauber and Gibbs sampling.
Exact simulation: coupling from the past
-
Exact simulation: Proof of Propp-Wilson thm
Application to the Ising model
See lecture notes 11.
-
Mini-project competition on Thursday, December 19, 12:15-2:00 PM, room INM 202
-
Project Deadline: Sunday, December 15, at 23:55.
-
Allowed material: four handwritten single-sided A4 pages