Master Common Sampling Techniques: Inverse Transform, Rejection, Importance & MCMC

Scenario Description

For a random variable we usually characterize its probability distribution using a probability density function (PDF). Given a value, the PDF yields its probability density; conversely, we can generate a value by sampling from the distribution, which is essentially the inverse use of the PDF. Sampling generally requires a suitable strategy based on the target distribution's characteristics.

Problem Description

Beyond distribution‑specific sampling methods, describe some general sampling methods or strategies you know, briefly outlining their main ideas and concrete steps.

Background Knowledge

Probability and Statistics, Sampling

Answer and Analysis

In previous sections we noted that most sampling methods start from uniform random numbers on [0,1]. Uniform random numbers can be generated by a linear congruential generator (LCG), which we assume is available.

For simple distributions we can use direct uniform‑based sampling (e.g., roulette‑wheel for finite discrete distributions). For many distributions, we resort to the transformation method. If a random variable x and a uniform variable u satisfy u = φ( x ), then their PDFs relate as p( u ) = p( x )·|φ'( x )|. Thus, if sampling x directly from p( x ) is difficult, we can transform to u , sample u easily, and obtain x via the inverse transformation x = φ⁻¹( u ). In higher dimensions the Jacobian determinant appears.

When φ is the cumulative distribution function (CDF), we obtain Inverse Transform Sampling. Assuming we can generate uniform u ∈[0,1], we compute x = F⁻¹( u ), where F is the CDF of the target distribution.

Steps for inverse transform sampling:

The resulting samples x_i follow the target distribution p( x ). Figure 1 illustrates the method.

If the CDF inverse is unavailable, we can use a proposal distribution q( x ) that is easy to sample and apply rejection sampling or importance sampling.

Rejection Sampling (Accept‑Reject)

Given target p( x ) and proposal q( x ) such that p( x ) ≤ M·q( x ), we repeatedly draw y∼q, u∼Uniform[0,1] and accept y if u ≤ p(y)/(M·q(y)). The accepted samples follow p( x ). Figure 2(A) shows the envelope function; adaptive rejection sampling refines the envelope for log‑concave targets (Figure 2(B)).

Importance Sampling

Used to estimate integrals of f( x ) under p( x ). We draw N samples x_i from a proposal q( x ) and weight them by w( x_i ) = p( x_i )/q( x_i ). The estimator of I[f] is (1/N)∑ f( x_i ) w( x_i ). When only sampling from p( x ) is needed, we can perform Sampling‑Importance Resampling (SIR): draw N samples from q, compute weights, and resample according to the weights to obtain samples approximately distributed as p( x ).

Markov Chain Monte Carlo (MCMC)

For high‑dimensional targets, rejection or importance sampling become inefficient. MCMC constructs a Markov chain whose stationary distribution is the target p( x ). Common algorithms include Metropolis‑Hastings and Gibbs sampling.

Metropolis‑Hastings (MH) Sampling

Given target p( x ), choose a proposal q( x*|x ). Generate a candidate x* from q, compute acceptance probability α = min{1, [p( x* ) q( x|x* )] / [p( x ) q( x* | x )]}, and accept or reject accordingly. Repeating this yields a chain that converges to p( x ).

Process steps illustrated in the following figure.

Gibbs Sampling

Gibbs sampling updates one dimension of the state vector at a time, sampling each coordinate from its conditional distribution given the others. Repeating this yields a chain converging to p( x ). The update order can be fixed or random.

Extension and Summary

We have listed several common sampling algorithms and briefly described their procedures. In interviews, candidates can be asked to choose a familiar algorithm, discuss its theoretical justification, advantages, disadvantages, and possible extensions.