Markov chains and algorithmic applications

COM-516

This file is part of the content downloaded from Markov chains and algorithmic applications.

Summary

This course is divided into two parts:

In the first part, we review important concepts about Markov chains: irreducibility, aperiodicity, recurrence, limiting and stationary distribution, the ergodic theorem, convergence speed towards equilibirum, spectral gap, cutoff phenomenon.
In the second part, we apply these concept to sampling, and more precisely to Markov Chain Monte-Carlo (MCMC) sampling, exploring various applications (function minimization, coloring problem, Ising model). In the last part of the course, we also look at exact simulation.