ISC 5228: Markov Chain Monte Carlo

Markov Chain Monte Carlo (MCMC) is one the most powerful and versatile methods developed in the 20th century. It uses a sequence of random numbers to solve important problems in physics, computational biology, econometrics, political science, Bayesian inference, machine learning, data science, optimization, etc. For many of these problems, simple Monte Carlo ("integration by darts") is inefficient. Often, MCMC is the answer.

Broadly speaking, MCMC is collection of sampling methods that allows us to solve problems of integration, optimization, simulation in high dimensional spaces. In this course, we will look at the foundations of Monte Carlo and MCMC, introduce and implement different sampling algorithms, and develop statistical concepts and intuition to analyze convergence and error in the simulation. Assignments and labs will consider illustrative examples from statistics, material science, physics, economics, optimization, and Bayesian inference.

Lectures

1. Introduction to Monte Carlo (pdf)

motivation; 1D integrals and average values; variation of error in MC and quadrature; 2D integrals; area of a circle

2. The Big Picture (pdf)

my big picture; connection between MC and MCMC.

3. Random Number Generation (pdf)

population and samples, random variables, PDFs and CDFs, expectation values; pseudorandom numbers, linear congruential generators, properties of good random number generators; standard 1D distributions, including discrete (uniform, binomial, Poisson) and continuous (normal, exponential).

4. Sampling 1D distributions (pdf)

Direct MC methods for sampling non-standard 1D distributions, including transformation method, and rejection sampling.

5. Error Analysis in direct MC (pdf, pdf)

propagation of error; central limit theorem and the error in direct Monte Carlo simulations; importance sampling as an error-reduction technique.

6. Multidimensional Distributions (pdf)

Joint, Marginal and Conditional Distributions; Bayes Theorem

7. Markov Chains (pdf)

Transition Probability Matrix, Detailed Balance

8. Metropolis Monte Carlo (pdf)

This lecture explains the basic algorithm, and applies it to two examples (1D and 2D examples)

9. MCMC Practicalities (pdf)

Burn-in, converegence, Gelman-Rubin diagnostic, autocorrelation and block-averaging

10. Metropolis-Hastings (pdf)

Using asymmteric proposals, example: lognormal distribution

11. Simulated Annealing (pdf)

Using MCMC-type simulation for global optimization, traveling salesman problem

12. MC3 (pdf)

Metropolis-coupled MCMC, tempering

13. Gibbs Sampling (pdf)

Clifford-Hammersley theorem, sampling from conditionals, relation to MCMC