Rejection Sampling

What Is Rejection Sampling?

Rejection sampling is a Monte Carlo method for generating random values from a target probability distribution that software cannot sample directly. Also called acceptance-rejection sampling, it draws candidates from an easier proposal distribution and accepts those that pass a probability-based test.

How Rejection Sampling Works

The proposal must cover every value the target can produce.

1. Define the target density or score function f(x).
2. Choose an easy-to-generate proposal distribution q(x).
3. Select a constant M such that f(x) ≤ Mq(x) for every candidate.
4. Generate a candidate x from q(x) and a uniform random value u between 0 and 1.
5. Accept x when u ≤ f(x) / [Mq(x)]. Otherwise, discard it.
6. Repeat until enough values are accepted. With a valid bound, they follow the target distribution.

A Simple Software Example

A simulator may need values from a custom two-peaked curve, while its library offers only uniform and normal generators. It can sample from a broad normal proposal and retain candidates based on the curve's height at each point. Visually, Mq(x) forms an envelope above the target curve. An unnormalized target score can be enough if the developer can establish a valid scaling bound.

Rejection Sampling vs. Importance Sampling

Both methods use a proposal distribution, but use candidate draws differently.

Benefits of Rejection Sampling

This approach works best when the proposal closely matches the target.

• It produces exact target-distribution samples when its assumptions hold.
• Accepted draws are independent, simplifying downstream analysis.
• Its logic is straightforward to prototype and test.
• It can work with unnormalized probability scores.
• It supports simulations, randomized tests, and synthetic-data workflows.

Practical Limits of Rejection Sampling

Efficiency depends on the proposal and bound.

• A loose envelope causes rejected candidates and wasted computation.
• The proposal must assign probability wherever the target does.
• Finding a safe, reasonably small M can be difficult.
• Performance often degrades in high-dimensional model spaces.
• Track the acceptance rate, then redesign the proposal or use another sampler if it remains low.

Using Rejection Sampling in AI and Application Development

Developers use rejection sampling in probabilistic software, model experiments, simulations, synthetic-data generators, and systems that quality-filter candidate outputs. It helps when a system can generate possibilities cheaply but needs a principled rule for retaining them. Teams can apply these ideas in app design and development, then build and test randomized workflows with an AI web app builder. Emergent helps teams turn these workflows into full-stack applications that can be tested and deployed.