MCMC (Markov Chain Monte Carlo)

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.