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.