Are rejected candidates always bad?

No. In classical rejection sampling, rejection is a probabilistic correction, not a judgment of quality.

Does the method always run quickly?

No. If acceptance is rare, many proposals are needed for each retained sample.

Is the target's normalizing constant always required?

Not necessarily. Suitable variants use an unnormalized target and a valid dominating envelope, but the acceptance rule must be derived consistently.

AI Glossary / Generative AI and language / Intermediate

Rejection sampling

Definition

Rejection sampling is a method for obtaining samples from a target probability distribution by generating candidates from a convenient proposal distribution and accepting only some of them. In its classical form, a mathematically defined acceptance probability corrects the proposal so that accepted samples follow the target. In AI discussions, the same phrase can also describe generating outputs and filtering them by a criterion; that broader usage should not automatically be assumed to have the classical distributional guarantee.

What it means

Some probability distributions are easy to evaluate but difficult to sample from directly. Rejection sampling uses another distribution that is easier to sample, then compensates for the difference through selective acceptance.

The rejected candidates are not necessarily erroneous observations. They are discarded as part of a sampling procedure designed to achieve the desired distribution among retained candidates.

The supplied term appears in a language-AI category, but the underlying statistical method is much broader. For language-model workflows, ask whether the author means exact sampling with a justified acceptance rule or a practical generate-and-filter procedure. These can have different purposes and guarantees.

How it works

For the normalized classical version, let p(x) be the target distribution and q(x) the proposal. Choose a finite constant M such that p(x) is no greater than M times q(x) everywhere the target has support.

Draw a candidate x from q and an independent uniform random number u between zero and one. Accept x if u is no greater than p(x)/(M q(x)); otherwise discard it and try again. The bound ensures this ratio is a valid probability.

With a correct bound and sampling procedure, accepted candidates follow p. For normalized p and q, the average acceptance probability is 1/M. A poor proposal or loose bound can therefore make the method expensive. Variants can use an unnormalized target with a corresponding valid envelope.

Three practical examples

1. A simulation project needs draws from an unusual distribution and uses a simpler proposal with a verified envelope to generate them.

2. A probabilistic-inference exercise samples complete scenarios and retains those matching observed evidence, illustrating why rare evidence can cause many rejections.

3. A language-data project generates candidate responses and filters those failing a quality rubric. It documents this as a filtering workflow and avoids claiming exact sampling from an unspecified ideal-response distribution.

Think of it this way

Think of a supplier delivering a convenient mixture of items while a receiving process retains different item types at carefully chosen rates. The retained mixture can differ from the delivered mixture.

The analogy has limits. To obtain a particular mathematical distribution, the retention rates must be correctly derived. Merely discarding items that look undesirable changes the mixture, but does not establish which target distribution has been achieved.

Worked example

Suppose the target has two outcomes, A and B, with probabilities 0.8 and 0.2. Use a proposal that produces each with probability 0.5. Choose M = 1.6, since the largest target-to-proposal ratio is 0.8/0.5 = 1.6.

Accept an A candidate with probability 0.8/(1.6 × 0.5) = 1. Accept a B candidate with probability 0.2/(1.6 × 0.5) = 0.25.

Across 1,000 proposals, the expected accepted counts are 500 A and 125 B. Among the expected 625 accepted candidates, the proportions are 80% A and 20% B, matching the target. Actual finite-run counts fluctuate. The expected acceptance rate is 625/1,000 = 0.625, which equals 1/M. No individual run must contain exactly these counts.

Illustrative case study

Fictional case: Alder Simulation needs a sample mix with many more routine scenarios than exceptional ones. Its initial generator produces the two types equally often, so the analysts implement a verified acceptance rule to obtain the intended mix.

They monitor both accepted outcomes and the total number of proposals. A later change to the proposal generator makes the old acceptance rule inappropriate. The team recalculates the rule before using the new generator's results.

The lesson is that the acceptance mechanism depends on the proposal. Keeping the same filtering code after changing the generator is not enough to preserve the target distribution.

Common misconceptions and mistakes

Rejection sampling is not the same as selecting the highest-scoring candidate from a fixed batch. Best-of-many selection creates its own output distribution and does not generally implement the classical acceptance rule.

Another mistake is choosing an envelope that fails to cover the target. Clipping acceptance probabilities at one does not automatically repair an invalid bound while preserving the desired distribution.

Rejected draws do not become negative training labels by definition. Finally, low acceptance can be a computational problem even when the method is mathematically correct. Efficiency and correctness are separate questions.

Business use

The method is useful in simulation and probabilistic modeling when a suitable proposal and acceptance calculation are available. Business teams evaluating such systems should ask about the target, proposal, acceptance rate, and evidence that the envelope is valid.

For generated-content filtering, define the actual quality criteria and inspect what the filter systematically excludes. A preference filter can narrow diversity or amplify evaluator mistakes. Report retained quality and generation cost together, and avoid describing filtered data as representative of a population unless the sampling design supports that claim.

Check your understanding

In the worked example, should every proposed B be rejected because B is less common in the target?

Answer: No. Accepting one quarter of B proposals preserves its required 20% share among accepted samples. Rejecting every B would produce the wrong target distribution.

Related terms

Learn next

Recalculate the two-outcome example with target probabilities 0.6 and 0.4 and the same uniform proposal. Find a valid M, derive both acceptance probabilities, and check the expected retained proportions. Then contrast that procedure with simply keeping the most highly scored candidate.

Sources

Sources: Carnegie Mellon University, Probabilistic Graphical Models lecture notes on Monte Carlo methods, https://www.cs.cmu.edu/~epxing/Class/10708-19/notes/lecture-13/ — primary course explanation of rejection sampling and envelope requirements. AIMA glossary repository, https://github.com/aimacode/aima-glossary/blob/master/glossary.md — supplied provenance; raw-file retrieval failed. Classical sampling is distinguished explicitly from loosely named language-output filtering. The numerical example and case are original.

Previous: Rejection region Next: Relatedness