Markov Chain Monte Carlo
- Definition
- Markov Chain Monte Carlo (MCMC) builds a Markov chain whose equilibrium distribution matches a complex probability distribution you want to sample from. You run the chain long enough and collect samples that approximate the target distribution. S, MCMC is handy when direct sampling is hard; it uses local moves to explore probability space. Unlike simple Monte Carlo, which samples independently, MCMC samples are correlated but allow exploration of high-dimensional distributions that would otherwise be infeasible.
How does it work?
MCMC constructs a sequence of proposals across the space and accepts or rejects them so that long runs produce samples from the desired distribution. Core steps: propose a move, compute acceptance probability, accept or reject, and repeat. Practical issues include burn-in, mixing, and autocorrelation which determine how many samples to keep or thin.
Examples
- Bayesian posterior sampling — Use MCMC (e.g., Metropolis-Hastings, Gibbs) to draw samples from complex posterior distributions in hierarchical models.
- Topic modelling (LDA) — Use collapsed Gibbs sampling to infer topic assignments for documents at scale.
- Phylogenetic inference — Sample tree-space posterior distributions for evolutionary models where direct computation is impossible.
Problems
- Slow mixing/convergence, especially in high dimensions
- Detecting when the chain has actually converged (burn-in diagnosis)
- Autocorrelation between samples reducing effective sample size
- Getting stuck in a single mode of a multimodal distribution
- Tuning proposal distributions or step sizes for efficient exploration