1. Definition

  • MCMC (Markov Chain Monte Carlo) is a class of algorithms used to sample from complex probability distributions, especially posterior distributions in Bayesian inference.
  • Instead of computing the distribution analytically (often impossible), MCMC generates a sequence of samples that approximate it.

In short: MCMC lets us approximate posteriors by simulation when math is too hard.

2. Key Ideas

  1. Markov Chain
    • A sequence of random states where the next state depends only on the current state (not the full history).
    • This dependence structure helps explore the probability distribution.
  2. Monte Carlo
    • Using repeated random sampling to approximate integrals and expectations.
    • Example: estimating $\pi$ by randomly sampling points inside a square and checking how many fall in a circle.
  3. Together (MCMC)
    • Build a Markov chain whose stationary distribution is the posterior distribution.
    • Run the chain long enough → samples approximate the posterior.

3. When Do We Use MCMC?

  • Posterior has no closed-form solution.
  • Distribution is high-dimensional or complex.
  • Used in Bayesian inference, machine learning, and computational statistics.

4. Common MCMC Algorithms

  1. Metropolis–Hastings Algorithm
    • Propose a new sample from a proposal distribution.
    • Accept or reject based on how likely it is under the target posterior.
  2. Gibbs Sampling
    • Special case of Metropolis–Hastings.
    • Sample each parameter conditionally on others.
    • Very useful in hierarchical models.
  3. Hamiltonian Monte Carlo (HMC)
    • Uses gradient information to make more efficient proposals.
    • Basis of Stan (Bayesian modeling software).
  4. No-U-Turn Sampler (NUTS)
    • An adaptive version of HMC.
    • Automatically decides step size and trajectory length.
    • Widely used in modern Bayesian packages (e.g., PyMC, Stan).

5. Example – Bayesian Coin Toss

  • Data: 7 heads, 3 tails.
  • Prior: Beta(2,2).
  • Posterior: $p \mid \text{data} \sim \text{Beta}(9,5)$.

This posterior has a closed form (Beta). But imagine it didn’t — then:

  • Use MCMC to generate thousands of samples of $p$.
  • Approximate posterior mean, variance, credible intervals.

6. Why It Works

  • We often want expectations like:

$E[f(\theta) \mid data] = \int f(\theta) P(\theta \mid data) d\theta$

  • Direct integration is hard in high dimensions.
  • MCMC approximates this integral by:

$E[f(\theta)] \approx \frac{1}{N} \sum_{i=1}^N f(\theta_i)$

where $\theta_i$​ are samples from MCMC.

7. Advantages

  • Works for very complex, high-dimensional distributions.
  • General-purpose method (flexible).
  • Provides full posterior samples (can compute any function of them).

8. Disadvantages

  • Computationally expensive.
  • Requires tuning (burn-in, thinning, proposal distributions).
  • Convergence diagnostics can be tricky (how do you know when chain “mixed” well?).

9. Applications

  • Bayesian inference (posterior estimation).
  • Hierarchical models (e.g., multi-level regression).
  • Machine learning (Bayesian neural networks, latent variable models).
  • Physics & Biology (complex simulation problems).

10. Key Takeaways

  • MCMC = simulate samples from a posterior distribution when it’s too hard to compute directly.
  • Relies on Markov chains to explore the distribution.
  • Famous methods: Metropolis–Hastings, Gibbs, HMC, NUTS.
  • Provides powerful tools for Bayesian modeling, though computationally intensive.

In short:
MCMC (Markov Chain Monte Carlo) is a set of algorithms to generate samples from complex posterior distributions. It combines Markov chains (sequential dependency) with Monte Carlo (random sampling) to approximate Bayesian inference when closed forms are impossible.