Sampling: Bootstrap, MCMC, Importance

Estimating Complex Distributions

In machine learning and statistics, we frequently encounter probability distributions $P(x)$ that cannot be integrated analytically.

Sampling Methods draw representative random data points from $P(x)$ to approximate expectations:

$$\mathbb{E}{P}[f(X)] = \int f(x) P(x) dx \approx \frac{1}{N} \sum{i=1}^N f(x_i), \quad x_i \sim P(x)$$

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│ 1. BOOTSTRAP RESAMPLING  │ 2. IMPORTANCE SAMPLING   │ 3. MCMC SAMPLING         │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ Resamples original data  │ Samples from easier      │ Constructs a Markov Chain│
│ WITH REPLACEMENT. Non-   │ proposal Q(x), weighting │ whose stationary state   │
│ parametric confidence.   │ by ratio P(x)/Q(x).      │ equals target P(x).      │
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

1. Bootstrap Resampling (Efron, 1979)

Given a dataset $D = {x_1, x_2, \dots, x_N}$:

How do we estimate the confidence interval of the median or mean without assuming a normal distribution?

  Original Dataset (N = 100) ──► Draw 1,000 Bootstrap Replicates (Size N with Replacement!)
                                            │
                                            ▼
  Calculate Median on Each Replicate ──► 2.5th & 97.5th Percentiles = 95% Confidence Interval!

Key Property

Sampling with replacement means each bootstrap sample leaves out approximately $36.8%$ of original rows (Out-Of-Bag / OOB Data), providing free validation datasets!

2. Importance Sampling

If target distribution $P(x)$ is difficult or slow to sample from directly:

Draw samples from a known, simpler Proposal Distribution $Q(x)$:

$$\mathbb{E}_P[f(X)] = \int f(x) \frac{P(x)}{Q(x)} Q(x) dx = \mathbb{E}_Q \left[ f(X) \frac{P(X)}{Q(X)} \right]$$

• Importance Weight: $w(x) = \frac{P(x)}{Q(x)}$ adjusts sample weights to correct for sampling from $Q$ instead of $P$.

3. Markov Chain Monte Carlo (MCMC)

Used in Bayesian inference to sample high dimensional un-normalized posterior distributions $P(\theta \mid D) \propto P(D \mid \theta) P(\theta)$.

MCMC constructs a Markov Chain whose stationary distribution equals target distribution $P(\theta)$:

Metropolis-Hastings Algorithm

1. Propose candidate parameter state $\theta^* \sim Q(\theta^* \mid \theta_{t-1})$.
2. Calculate Acceptance Probability $\alpha$:

$$\alpha = \min\left(1, ; \frac{P(\theta^) Q(\theta_{t-1} \mid \theta^)}{P(\theta_{t-1}) Q(\theta^* \mid \theta_{t-1})}\right)$$

3. Draw $u \sim U(0, 1)$. If $u \le \alpha$, accept $\theta_t = \theta^*$; else reject and keep $\theta_t = \theta_{t-1}$.

Gibbs Sampling

Special case of Metropolis-Hastings where each parameter $\theta_j$ is sampled directly from its conditional distribution $P(\theta_j \mid \theta_{-j}, D)$, yielding an acceptance rate $\alpha = 1.0$.

Say this out loud

Bootstrap resampling estimates confidence intervals non parametrically by drawing repeated samples with replacement. Importance sampling draws samples from a simpler proposal distribution Q, weighting samples by ratio P over Q. MCMC constructs a Markov Chain whose stationary distribution matches complex un normalized posterior distributions using Metropolis Hastings or Gibbs sampling.

Followups to expect

1. What is Burn-in in MCMC? Discarding the initial $N$ iterations (e.g. first 1,000 samples) of an MCMC chain to allow the Markov chain to converge to its stationary target distribution from arbitrary initialization.
2. What is Hamiltonian Monte Carlo (HMC)? An advanced MCMC algorithm (used in Stan) that uses physics gradient dynamics to propose distant parameter jumps, scaling far better in high dimensions than random walk Metropolis-Hastings.