Course: Markov chains and algorithmic applications

Weekly outline

General
General
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%

Course 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
Week 1 (September 19-20)
Week 1 (September 19-20)
General introduction, Markov chains, classification of states, periodicity
Week 2 (September 26-27)
Week 2 (September 26-27)
Recurrence, transience, positive/null-recurrence
Week 3 (October 3-4)
Week 3 (October 3-4)
Stationary and limiting distribution, two theorems
Week 4 (October 10-11)
Week 4 (October 10-11)
Proof of the ergodic theorem, coupling argument
- lecture_notes4.pdf File
- Homework 4 File
Week 5 (October 17-18)
Week 5 (October 17-18)
Detailed balance, rate of convergence, spectral gap, mixing times
- lecture_notes5.pdf File
- Homework 5 File
Week 6 (October 24-25)
Week 6 (October 24-25)
Rate of convergence: proofs
- lecture_notes6.pdf File
- Homework 6 File
Week 7 (October 31-November 1)
Week 7 (October 31-November 1)
Reflection principle, arcsine law, cutoff phenomenon
- lecture_notes7.pdf File
Week 8 (November 7-8)
Week 8 (November 7-8)
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
Week 9 (November 14-15)
Week 9 (November 14-15)
Sampling: introduction and general methods, Metropolis-Hastings algorithm
Week 10 (November 21-22)
Week 10 (November 21-22)
Applications: function minimization, coloring problem
Week 11 (November 28-29)
Week 11 (November 28-29)
Ising model, Glauber dynamics
Week 12 (December 5-6)
Week 12 (December 5-6)
Exact simulation: coupling from the past
Week 13 (December 12-13)
Week 13 (December 12-13)
Exact simulation: application to the Ising model
Week 14 (December 19)
Week 14 (December 19)
Mini-project competition on Thursday, December 19, 12:15-2:00 PM, room INM 202