← All posts

What Is Rejection Sampling?

In Apple Game, every board looks random, but the digits always sum to a multiple of 10. How do you generate random data that satisfies a constraint like that? One simple way is rejection sampling. It is a general technique that comes up in many places, so it is worth understanding on its own.

The idea

Rejection sampling is a method for generating random samples that satisfy some constraint. The recipe is straightforward: generate a candidate from an easy-to-sample distribution, check whether it meets the constraint, and either keep it or throw it away. If you threw it away, try again.

That is it. You do not need to figure out how to directly sample from the constrained distribution. You just need two things: a way to generate candidates and a way to check them.

The algorithm

function RejectionSample(Generate, Satisfies): Sample;
var
  candidate: Sample;
begin
  repeat
    candidate := Generate();
  until Satisfies(candidate);
RejectionSample := candidate;
end;

Generate a random candidate. Check the constraint. If it passes, keep it. If not, throw it away and try again. Each attempt is independent, so the process is memoryless.

Examples

Sampling points inside a circle. Say you want uniformly random points inside a unit circle. Sampling directly from a circular region is a bit annoying. One simple way: sample a point uniformly from the bounding square (pick x and y each between -1 and 1). Then check if x² + y² ≤ 1. If it is inside the circle, keep it. Otherwise reject and try again. Since the circle covers about 78.5% of the square, roughly 4 out of 5 candidates pass. Very efficient.

Generating valid passwords. Suppose you need a random password that contains at least one uppercase letter, one digit, and one special character. One approach: generate a random string of the required length from the full character set, then check if it meets the rules. If it does, use it. If not, generate another one. For typical password lengths (12+ characters), most random strings will pass, so you rarely need more than a few tries.

Random points sampled uniformly from a square. Points inside the circle are accepted (blue); points outside are rejected (gray).

Why it is useful

The main appeal is simplicity. You do not need to derive a specialized sampling algorithm for your constrained distribution. As long as you can generate candidates and check constraints, you are set. The implementation is usually just a while loop with a random generator and an if statement.

This is useful when the constraint is easy to verify but hard to bake into the generation process directly. Many real-world problems have this shape.

The main limitation: acceptance rate

Rejection sampling works well when a reasonable fraction of candidates pass the check. The key quantity is the acceptance rate — the probability that a random candidate satisfies the constraint.

If the acceptance rate is 1 in 10, you need on average 10 candidates per accepted sample. That is fine. If it is 1 in a million, you are generating a million candidates to keep one. That is not fine.

In high-dimensional spaces, acceptance rates can get very small. If you are trying to sample from a tiny region of a 100-dimensional space by generating points uniformly in the bounding box, almost every candidate will miss. This is where rejection sampling breaks down and you need smarter methods (MCMC, importance sampling, etc.).

In practice, rejection sampling is a good first choice when the acceptance rate is reasonable — say, above 1% or so. Below that, you should look for alternatives.

Back to Apple Game

In Apple Game, a randomly generated board has about a 1 in 10 chance that its digit sum is divisible by 10, so the acceptance rate is around 10%. That makes rejection sampling efficient here — on average, you only need about 10 tries to get a valid board.