What is rejection sampling?

In this article

1. Before you start
2. Why interviewers ask this
3. Rejection sampling from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

A candidate who can state the accept-or-reject rule but cannot say what it costs will be stopped by the acceptance-rate question, because the rule alone says nothing about cost. The method is a compact test of three skills: reading a density as an area, bounding one curve by another, and reasoning about how a cost grows with dimension. It appears in statistics, simulation and classical machine learning interviews, and it has a second life in language-model training, where the same name describes selecting the best of several generated answers.

A weak answer says "sample, then reject the bad ones". A strong answer names the proposal, names the constant, states that the acceptance rate is one over that constant, and says why the method is a one-dimensional tool.

Rejection sampling from first principles

In plain words

Rejection sampling

Rejection sampling is a procedure that generates independent samples from a target density by drawing candidates from a simpler proposal density and accepting each candidate with probability equal to the target density divided by a scaled copy of the proposal density.

Proposal distribution

A proposal distribution is an easy-to-sample density, written g, that supplies the candidate values and must be positive everywhere the target density is positive.

Envelope constant

The envelope constant, written c and also called the rejection constant, is a number at least one chosen so that c times the proposal density lies on or above the target density at every point.

Acceptance rate

The acceptance rate is the share of candidates that are kept, which equals one divided by the envelope constant when both densities are properly normalised.

Picture a rectangular dartboard with the curve you want drawn on it as a hill. Throw darts so that they land evenly anywhere. Keep only the darts that landed under the hill, and note where along the bottom edge each one fell. Those positions bunch where the hill is tall and thin out where it is low. That is what a sample from the hill's distribution looks like.

The analogy breaks in one place. A real board is flat with a top edge. In rejection sampling the "board" is the proposal curve scaled up by c, so its height changes from place to place. The darts land evenly under that curve, not across a rectangle. In one precise sentence: you throw points evenly under a curve that you can sample from and that sits above the target, and you keep the points that land under the target.

Step 1: Choose a proposal g

The first step picks a density g that is easy to sample and that is positive wherever the target f is positive. Devroye's survey states the requirement as f(x) ≤ c·g(x) for all x, for some finite constant c ≥ 1, which he calls the rejection constant; Step 2 finds that constant. Von Neumann proposed the method in 1951, according to the same survey.

The inputs are the target f, which you can evaluate but cannot sample, and a family of easy densities such as the uniform or the exponential. The output is g. For a target on the interval from zero to one, the flat density g(x) = 1 is the simplest choice. The choice matters because the tails of g must stay above the tails of f: a g that decays faster than f has no finite c.

What you now know: you have an easy density whose scaled copy can cover the target.

Step 2: Find c, the maximum of f over g

The envelope constant c is the largest value of f(x) divided by g(x), and finding it is the only analytic work in the method. Devroye notes that the method "requires some analytic work, notably to determine c", and that you only need the ratio f(x) / (c·g(x)), so normalising constants cancel.

For the target Beta(2, 5), the density is f(x) = 30·x·(1−x)^4 on the interval from zero to one, and it peaks at x = 0.2, where it equals 2.4576¹. With the flat proposal g = 1, the smallest valid constant is therefore c = 2.4576. The interview consequence is that "accept with some probability" is not an answer; "accept with probability f / (c·g), where c is the maximum of f / g" is.

The input is the ratio f/g over the whole range. The output is its maximum. A c of 1.5 lies below the density between x of about 0.07 and 0.41, so it is too small¹. Any larger c is valid but slower; any smaller c is wrong.

Text description of the diagram

• The density 30x(1-x)^4 peaks at 2.4576 where x is 0.2.
• With a flat proposal, c of 2.4576 covers the target everywhere.
• A c of 1.5 lies below the density between x of about 0.07 and 0.41, so it is too small.

Step 3: Propose, then test

Each round draws a candidate x from g and an independent uniform number u between zero and one, then keeps x when u·c·g(x) ≤ f(x). In Devroye's pseudocode this is "repeat: generate U uniformly on [0, 1]; generate X with density g; until U·c·g(X) ≤ f(X); return X". Equivalent wording: accept x with probability f(x) / (c·g(x)).

Why the kept values have the right density: the pair (x, u·c·g(x)) is uniform under the curve c·g, and keeping the pairs that fall under f leaves points uniform under f. MacKay (2003), section 29.3 gives the same argument: the accepted points are uniformly distributed under the target curve, so their x-coordinates are independent samples from it.

The input is one candidate and one uniform number. The output is either a sample or nothing, and the rejected round is simply repeated.

Step 4: Count the cost, which is c draws per sample

The acceptance rate is one over c, so on average c candidates are drawn for each sample kept. Devroye states that "the expected number of iterations before halting is c, so the rejection constant must be kept small", and MacKay reasons that the rate is the area under f divided by the area under c·g, which is 1/c for normalised densities.

For Beta(2, 5) with a flat proposal, 1,000,000 candidates gave 406,726 accepted, an acceptance rate of 0.4067 against the predicted 1 / 2.4576 = 0.4069¹. The accepted values had mean 0.2855 against the true 0.2857, and a Kolmogorov-Smirnov (KS) test of the accepted values against the Beta(2, 5) distribution gave a statistic of 0.00096 and a p-value of 0.847, so the sample is consistent with the target¹.

What you now know: the method is exact for any valid c, its cost is c, and a tight bound is the whole game. The figure below traces the four steps.

1 · Choose g2 · Find c3 · Propose and test4 · CostReplay

Step-by-step description

1. Pick an easy density g that is positive wherever f is.
2. Take c as the maximum of f(x) over g(x), so f is at most c times g.
3. Draw x from g and u from 0 to 1; keep x if u times c times g(x) is at most f(x).
4. A share of 1 over c is kept, so c draws make one sample.

• The requirement is f(x) ≤ c·g(x) for all x, for some finite constant c ≥ 1.
• A value x is kept when u times c times g(x) is at most f(x).
• The acceptance rate is 1 over c, and c is the expected number of proposals per sample.

Worked example

The worked example samples from Beta(2, 5) with a flat proposal and then from a half-normal distribution with an exponential proposal, and compares the measured acceptance rate with one over c.

Each row used 1,000,000 candidates and seed 0¹. For the half-normal target f(x) = 2·φ(x) on x ≥ 0, where φ is the standard normal density, with proposal g(x) = e^(−x), the ratio f/g is largest at x = 1, where it equals the square root of 2e/π, about 1.3155. Devroye's survey derives the same expression, √(2e/π), for a standard normal target with a Laplace proposal. The measured acceptance of 0.7609 means about three of every four candidates are kept.

The bound matters more than any other choice. With c = 1.5, below the true maximum of 2.4576, the method accepts more often (0.5254) but returns the wrong distribution: the sample mean is 0.3029 against 0.2857, and the KS test gives a p-value that rounds to zero¹. With c = 5 the output is correct but only one candidate in five is kept, because one over five is 0.2.

Text description of the diagram

• With c of 1.5 the sample mean is 0.3029 against a true 0.2857.
• With c of 2.4576 the acceptance rate is 0.4067.
• With c of 5 the acceptance rate is 1 over 5, or 0.2.

Trade-offs and edge cases

Rejection sampling is exact and simple, and its cost grows exponentially with the number of dimensions. MacKay's case study takes a Gaussian target and a proposal Gaussian whose standard deviation is 1% larger in every one of N dimensions: the constant is c = (σ_Q/σ_P)^N, which for N = 1000 is about 20,000, so the acceptance rate is about 1 in 20,000¹. He concludes that the method "is not expected to be a practical technique for generating samples from high-dimensional distributions".

A simulation at d = 10 with a 10% wider proposal gave an acceptance rate of 0.3872 against the predicted 0.3855¹.

Text description of the diagram

• With a proposal 10 percent wider, acceptance is 0.9091 in one dimension and 0.3855 in ten.
• At 50 dimensions it is 0.008519, and at 100 dimensions it is 0.00007257.
• With a proposal 1 percent wider it is 0.3697 at 100 dimensions.

Three more limits apply. First, the bound has to exist: g must be positive wherever f is, and for a Gaussian target and a Gaussian proposal, the proposal must be at least as wide (equal spreads give c = 1), because MacKay notes that if it is narrower, "there is no c such that c Q exceeds P for all x"; a heavier-tailed proposal such as the exponential in the worked example avoids this.

Second, finding c can be hard when you do not know where the target peaks. Third, the target may be unnormalised: the method needs only the ratio f/(c·g), so a density known up to a constant works, but then the acceptance rate is no longer 1/c unless you rescale.

The high-dimensional tool is Markov chain Monte Carlo (MCMC), such as Metropolis–Hastings, which MacKay (§29.4) presents after rejection sampling because its proposal depends on the current state; it appears in deep learning work on generative models, and its samples are correlated rather than independent. Importance sampling, which keeps every draw and reweights it by f/g, is no escape: MacKay (§29.2) shows that in high dimensions a few draws receive huge weights and dominate the estimate, so it degrades too. Rejection sampling stays the standard tool for one or two variables and for the inner loop of other samplers, for example to draw one component at a time.

The same name in language-model training

In language-model training, "rejection sampling" means sampling several answers and keeping the best one by score. The Llama 2 paper (v2, July 2023) describes it as sampling K outputs from the model, selecting the best with a reward model (a separate model that scores how good an answer is), and using the selected outputs for a gradient update.

It was done only with the largest 70-billion-parameter chat model, and the smaller models were trained on that data. The Llama 3 paper (July 2024) samples K "typically between 10 and 30" outputs per prompt. The reward model is trained with the kind of loss the entropy and cross-entropy page explains. This is a selection rule borrowed from the statistical method's name, not the f/(c·g) test above, and the two should not be confused in an interview.

Generating K answers per prompt is the same repeated-sampling workload that serving a large language model (LLM) has to make cheap. As an illustration of why more samples help, if the reward of each answer were a standard normal number, the expected best of K draws rises from about 1.03 at K = 4 to 1.54 at K = 10 and 2.04 at K = 30¹. The gain flattens, so each extra sample buys less than the last.

How to answer it in an interview

The spoken structure is: say the rule, say that the kept samples are exact, then give the cost and the point where it stops being practical.

Common mistakes

• "Pick any c, it only changes the speed" (wrong). A c below the maximum of f/g gives a biased distribution; in the example c = 1.5 moved the mean from 0.2857 to 0.3029 (right: any c at or above the maximum is exact and only costs speed).
• "The acceptance rate is c" (wrong). The expected number of candidates per sample is c, and the acceptance rate is its inverse, 1/c (right).
• "The rejected draws are wasted and bias the result" (wrong). Rejection is what removes the mismatch between g and f; the accepted values are independent and exact (right).
• "It works fine in a thousand dimensions if the proposal is close" (wrong). A proposal 1% too wide per dimension still gives about 1 acceptance in 20,000 at 1,000 dimensions (right: use MCMC such as Metropolis–Hastings there).
• "Rejection sampling in Llama is this algorithm" (wrong). The language-model use keeps the best of K by a reward score and does not test u against f/(c·g) (right).

Follow-up questions

What is the acceptance rate of rejection sampling, and what happens if c doubles?

The acceptance rate is 1/c when both densities are normalised, because it is the area under the target divided by the area under c times the proposal. For Beta(2, 5) with a flat proposal it is 1/2.4576, about 40.7%. If c doubles, the expected number of candidates per sample doubles and the acceptance rate halves, but the samples stay exact.

Do you need the normalising constant of the target to use rejection sampling?

No. The test u·c·g(x) ≤ f(x) works with f known only up to a constant, because Devroye notes that normalising constants cancel in the ratio. The cost is that you must bound the unnormalised f, and 1/c is then not the acceptance rate.

Why does rejection sampling fail in high dimensions, and does importance sampling fix it?

The constant c has to cover the target's tallest point in every dimension at once, and for Gaussians it grows like (σ_Q/σ_P)^d, which is exponential in d. At 100 dimensions a 10% wider proposal accepts about 0.007% of candidates. Importance sampling does not fix it, because a few huge weights dominate in high dimensions (MacKay §29.2); MCMC is the usual tool.

Why is rejection sampling unbiased?

Points drawn evenly under c·g and kept only when they fall under f are uniform under f, so their x-coordinates have density f exactly. Rejection removes the mismatch between g and f instead of adding bias, and each round is independent.

We want points uniform in the unit square that stay within the unit circle. How do you do it?

Draw x and y uniformly from 0 to 1 and keep the pair when x² + y² ≤ 1, which is rejection with a flat proposal. The acceptance rate is the quarter-circle's area, π/4 ≈ 0.7854 (simulated 0.7853), so the expected draws per kept point are 4/π ≈ 1.27¹.

What is the expected number of rand7 calls to build rand10?

Two calls give one of 49 equally likely pairs, so number them 0 to 48, keep the 40 numbers below 40 and map them to digits by the remainder after dividing by 10; reject the other 9 and redraw. The acceptance is 40/49, so the expected pairs are 49/40 = 1.225 and the expected calls are 2·49/40 = 2.45 (simulated 2.45)¹.

Sources

1. Non-Uniform Random Variate Generation (survey chapter, section 1.7 The rejection method; page undated, read 2026-10-24) — Luc Devroye, McGill University, 24 Oct 2026
2. Information Theory, Inference, and Learning Algorithms, chapter 29.3 Rejection sampling — Cambridge University Press (MacKay), 1 Sep 2003
3. Llama 2 paper, open foundation and chat models (arXiv 2307.09288 v2) — arXiv (Touvron et al.), 19 Jul 2023
4. The Llama 3 Herd of Models (arXiv 2407.21783) — arXiv (Llama Team, Meta), 31 Jul 2024