Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 38 · Sampling Methods

Acceptance–Rejection Sampling

Sample from awkward densities by proposing from an easy distribution and accepting with the right probability. Build it, test it and tune its efficiency.

Sometimes you know a density f(x) but cannot invert its CDF. Acceptance–rejection sampling (also called rejection sampling) handles this beautifully. You draw candidates from a simple distribution and keep each one with a probability that corrects the shape. It is the same dart-throwing idea you used to estimate π, now used to generate random numbers.

The dartboard picture

Imagine the graph of the density f(x). Under the curve lies a region of area 1. If you throw darts uniformly into a box that contains the whole curve and keep only the darts that land under the curve, then the x coordinates of the kept darts follow the density f. Taller parts of the curve catch more darts.

flowchart TD
  A["Draw x from proposal g"] --> B["Draw u uniform on 0 to 1"]
  B --> C{"u ≤ f(x) / (M g(x)) ?"}
  C -->|"yes"| D["accept x"]
  C -->|"no"| A

Rejection sampling: propose, then accept with probability f(x)/(M·g(x)).

The algorithm

You need a proposal density g(x) that is easy to sample and a constant M with

Text
f(x) ≤ M · g(x)   for all x.

Then repeat:

  1. Draw x from g.
  2. Draw u uniform on (0, 1).
  3. If u ≤ f(x) / (M·g(x)), return x. Otherwise try again.

The returned values have density exactly f. The probability of accepting any single proposal is 1/M, so the expected number of proposals per sample is M. A tighter bound (smaller M) means less waste.

An important extra: f only needs to be known up to a constant. If you know f̃(x) ∝ f(x), use f̃ and a bound f̃ ≤ M g. The method still returns draws from the normalized f. This is crucial for Bayesian statistics, where normalizing constants are hard to compute.

Example: density 6x(1−x) on [0, 1]

This is the Beta(2, 2) density, a smooth hump. Its maximum is at x = 0.5 where f = 1.5. Use a uniform proposal g = 1 on [0, 1] and M = 1.5. The acceptance probability is f(x)/1.5, and we expect to accept 1/M = 2/3 of the proposals.

Python Rejection sampler for 6x(1-x)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Beta(2, 2) variance is αβ/((α+β)²(α+β+1)) = 4/(16·5) = 0.05.

A better proposal: efficiency

The choice of g decides speed. If g mimics f, M is close to 1 and few samples are wasted. Consider the half-normal density f(x) = √(2/π) e^(−x²/2) for x ≥ 0 (a normal folded onto the positive side). An exponential proposal g(x) = e^(−x) works, with

Text
f(x)/g(x) = √(2/π) · e^(−x²/2 + x),  which peaks at x = 1.
M = √(2/π) · e^(1/2) = √(2e/π) ≈ 1.3155.

The acceptance probability is f(x)/(M g(x)) = e^(−(x−1)²/2). Flipping the sign of the result at random gives a full standard normal, which is the classic textbook way to sample normals by rejection.

Python Half-normal from an exponential proposal

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

About 76% of proposals are accepted, so the sampler is efficient. Compare this with a uniform proposal on a wide interval, which would waste most points on the empty tails.

Pitfalls

  • Unbounded ratio. If f/g has no upper bound (for example a heavy-tailed f and light-tailed g), no finite M exists. The proposal must have tails at least as heavy as the target.
  • A bad bound. If your M is too small, the sampler silently returns wrong samples; if too large, it is just slow. Check f(x) ≤ M g(x) over a fine grid.
  • High dimensions. In many dimensions the acceptance probability collapses, because a simple proposal covers a vast empty space. This is a main motivation for Markov chain Monte Carlo (Chapter 6).

A wrong M produces no error message, only subtly wrong samples. Always test a rejection sampler: compare a histogram with the density and run a KS test, as above.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In rejection sampling with f ≤ M·g, what is the probability that a single proposal is accepted?

    Averaged over proposals, the acceptance probability is ∫ f/(M g) · g dx = 1/M.
  2. 2. Which proposal property is necessary?

    The bound f ≤ M g is what makes the acceptance probability f/(M g) a valid probability.
  3. 3. A sampler uses M = 4. About how many proposals are needed for 1,000 accepted samples?

    The acceptance rate is 1/M = 1/4, so you need about 1,000 × 4 = 4,000 proposals.
  4. 4. Why can rejection sampling work even if f is known only up to a constant?

    The accepted draws have density proportional to the unnormalized function used, so the normalizing constant is never needed.

Summary

  • Propose x from an easy density g, accept with probability f(x)/(M g(x)), repeat.
  • Accepted samples have exactly the target density; the acceptance rate is 1/M.
  • A proposal close in shape to f makes M near 1; the proposal's tails must dominate the target's.
  • It works for unnormalized densities, which matters in Bayesian statistics.
  • It degrades in high dimensions, which motivates MCMC.

Next: Sampling Discrete Distributions