CMPSC 292A MCMC Algorithms

This course studies Markov Chain Monte Carlo (MCMC) algorithms. MCMC algorithms are a widely used tool for sampling from distributions defined over a huge combinatorial set.  It is often easy to define a Markov chain with the desired distribution as its equilibrium distribution but it is difficult to design a chain which converges efficiently and to determine convergence. This is a theoretical course focusing on mathematical tools for analyzing the convergence rate of Markov chains.  This course is appropriate for both undergraduate and graduate students with a background in the analysis of algorithms and discrete mathematics.