RejectionSampling

Rejection sampling is a basic Monte Carlo method for drawing samples from a target probability distribution by using a simpler, easy-to-sample proposal distribution. It works by generating candidates from the proposal and accepting them with a probability that corrects for the mismatch between the target and the proposal. The target distribution is described by its density π(x) with respect to a common measure, and the proposal distribution has density q(x). A constant M ≥ sup_x (π(x)/q(x)) is required so that π(x) ≤ M q(x) for all x. If the target density is known only up to a normalization constant, one can use an unnormalized f(x) ∝ π(x) and require f(x) ≤ M q(x).

Algorithm: Repeat until a sample is accepted. Draw X from the proposal density q(x). Draw U from the uniform distribution on [0, 1]. Accept X if U ≤ π(X)/(M q(X)) (or U ≤ f(X)/(M q(X)) with an unnormalized f). The accepted X is a sample from the target distribution π. If π is normalized, the average acceptance probability is 1/M, so a smaller M yields higher efficiency.

Choice of proposal and efficiency: The efficiency of rejection sampling hinges on how closely q(x) covers π(x) and on the tightness of M. A good proposal closely approximates the target when scaled, minimizing M and maximizing acceptance rate. The method is exact in the sense that accepted samples are distributed according to π, provided the conditions hold.

Limitations and variations: Rejection sampling can be inefficient if M is large or if the target is high-dimensional, as acceptance rates can become very small. Variants include adaptive rejection sampling, which builds a changing envelope for certain log-concave targets, and other specialized schemes that improve efficiency for specific classes of distributions. Rejection sampling remains a foundational technique in Bayesian inference and statistical simulation due to its simplicity and exactness.