Sampling and MCMC

When the posterior $P(X | E)$ is intractable to compute exactly, generate samples from it instead. Aggregate the samples to estimate any quantity of interest.

Rejection sampling

Sample from the prior $P(X)$. Keep only samples consistent with the evidence $E$. Compute statistics on the kept samples.

Simple, but in high-dimensional or low-prior-on-evidence cases, the rejection rate approaches 100% — most samples are thrown away. Not practical for anything but toy problems.

Importance sampling

Sample from a *proposal* distribution $Q(X)$ and weight each sample by $P(X, E) / Q(X)$. Reduces rejection but variance depends critically on how close $Q$ is to the true posterior. Poor proposals give catastrophic variance.

Markov Chain Monte Carlo (MCMC)

Construct a Markov chain whose stationary distribution is the desired posterior. Run the chain; eventually samples come from the posterior.

### Gibbs sampling

For each variable $X_i$, given all other variables' current values, sample $X_i$ from $P(X_i | X_{-i})$. Cycle through variables.

The full conditional $P(X_i | X_{-i})$ in a Bayes net is just the product of the factors involving $X_i$ — easy to compute even when the full joint is hard.

### Metropolis-Hastings

Propose a new state $X'$ from a proposal $Q(X' | X)$. Accept with probability

If accepted, move to $X'$. Otherwise stay. The accept-reject step ensures the chain converges to $P$. Works even when you can only compute $P$ up to a normalization constant — huge in Bayesian inference.

Diagnosing convergence

The biggest practical issue with MCMC. Standard tools:

• Effective sample size (ESS): how many independent-equivalent samples you have.
• Gelman-Rubin $\hat{R}$: compare within-chain and between-chain variance. $\hat{R} \approx 1$ suggests convergence.
• Trace plots: visual sanity check.

Real chains exhibit slow mixing, autocorrelation, and "stuck" states. Diagnostics are necessary, not optional.

Modern alternatives

• Hamiltonian Monte Carlo (HMC) / NUTS: use gradient information for far more efficient exploration. Standard in Bayesian modeling tools (Stan, PyMC, NumPyro).
• Variational inference: approximate the posterior with a simpler distribution by minimizing KL divergence. Fast but biased; complements MCMC.
• Particle filters: sequential MCMC for state-space models.

When to use what

• Conjugate priors, small problems: exact inference.
• Bayesian models with continuous parameters: HMC/NUTS via Stan or NumPyro.
• Large datasets, willing to accept approximation: variational inference.
• Discrete graphical models: Gibbs / Metropolis-Hastings.