type: concept topic: Rejection Sampling course: STA414 tags:

  • MachineLearning

Rejection Sampling

Rejection Sampling generates samples from a target density $f(x)$ indirectly by using a proposal density $g(x)$ that is easy to sample from.

1. Setup

The method requires three ingredients:

  • Target density: $f(x)$, the distribution of interest
  • Proposal density: $g(x)$, a distribution that can be sampled directly
  • Envelope constant: $C$, chosen so that
$$f(x) \leq C\,g(x) \quad \text{for all } x$$

Thus $C\,g(x)$ forms an envelope above $f(x)$.

2. Algorithm

Repeat until a sample is accepted:

  1. Draw
$$Y \sim g$$
  1. Draw
$$U \sim \mathrm{Uniform}(0,1)$$

independently of $Y$.

  1. Accept $Y$ if
$$U \leq \frac{f(Y)}{C\,g(Y)}$$

Otherwise reject $Y$ and repeat.

An accepted $Y$ is a sample from the target density $f$.

3. Core Acceptance Condition

The acceptance test can be rewritten as

$$U \cdot C\,g(Y) \leq f(Y)$$

This is the central condition of the algorithm.

4. Geometric Interpretation

The curve $C\,g(x)$ acts as a roof above the target density $f(x)$.

Sampling $Y \sim g$ chooses a horizontal location.
Sampling $U \sim \mathrm{Uniform}(0,1)$ generates a vertical fraction of the roof height at that location.
The quantity $U \cdot C\,g(Y)$ is therefore a random height between $0$ and $C\,g(Y)$.

  • If this height is below $f(Y)$, accept the point
  • If it is above $f(Y)$, reject the point

Thus acceptance means the sampled point falls under the target density rather than only under the envelope.

5. Example: Sampling from Beta$(2,2)$

Suppose the target density is

$$f(x)=6x(1-x), \quad x\in[0,1]$$

Choose the proposal

$$g(x)=1, \quad x\in[0,1]$$

which is the density of $\mathrm{Uniform}(0,1)$.

Since the maximum of $f(x)$ is

$$f(0.5)=1.5$$

we can choose

$$C=1.5$$

Then

$$C\,g(x)=1.5$$

is a valid envelope.

If a proposal draw gives

$$Y=0.3$$

then

$$f(0.3)=6(0.3)(0.7)=1.26$$

and

$$\frac{f(Y)}{C\,g(Y)}=\frac{1.26}{1.5}=0.84$$

So:

  • if $$U=0.65$$, accept because $$0.65 \leq 0.84$$
  • if $$U=0.92$$, reject because $$0.92 > 0.84$$

6. Key Requirement

The method only works if the proposal dominates the target everywhere through

$$f(x) \leq C\,g(x)$$

If this fails at any point, the acceptance probability is invalid.

Beta(2,2) via g = U(0,1)

Pasted image 20260318023705

Multimodal Gaussian Mixture via U(0,1)

$$f(x) = e^{-0.5(x-3)^2} + 0.7 \cdot e^{-0.5((x-7)/0.5)^2}, \quad x \in [0, 10]$$

Pasted image 20260318023735