CoreSource checked

Rejection Sampling

Samples from a target distribution by rejecting some easier samples.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Randomness & Sampling
Difficulty: Intermediate
Family: Sampling
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 14
Code example: Ready
Visualization: Ready

Overview

Rejection Sampling draws from a proposal distribution and accepts only samples that pass a probability test.

Core Concepts

proposal distributionacceptance testtarget densityrandom drawsample selectionrandom samplingsamplingrandom source

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(k)

Average

O(k / a)

Worst

O(k / a)

Space

O(k)

When to Use

Use Rejection Sampling when you need to draw candidate samples.
Use it for sampling hard distributions with inputs like target density.
Use it when randomization, representative samples, or controlled variation are needed.
Use it when the Sampling tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when repeatability is required but seeds and random sources are not controlled.
Avoid it when reproducibility, distribution quality, or sample independence cannot be verified.
Avoid it when the required output is not accepted samples.

What It Does

Draws candidate samples
Accepts candidates with a target-based rule

Use Cases

Sampling hard distributions
Monte Carlo methods
Probabilistic modeling

Inputs

Target density
Proposal sampler
Envelope bound

Outputs

Accepted samples

Key Formulas (1)

Acceptance test

accept if u ≤ target(x) / (M · proposal(x))

accept if u <= target(x) / (M * proposal(x))

Accepts proposals in proportion to how well they match the target distribution.

Pseudocode

1.Draw a candidate from the proposal distribution
2.Draw a uniform random threshold
3.Compare the threshold with the target-to-envelope ratio
4.Keep the candidate if it passes
5.Repeat until enough samples are accepted

Canonical Example

Input: items = [A, B, C, D], seed = 7
Output: sampled or randomized result
Explanation: Rejection Sampling: The algorithm uses controlled randomness to choose or generate values.

Implementation Notes

Keep the input contract explicit: Target density; Proposal sampler; Envelope bound.
Thread a seedable random source through the implementation for repeatable tests.
Separate the random number source from the algorithm so tests can use fixed seeds.
Separate the random source from the sampler so tests can use fixed seeds and distribution checks.

Common Pitfalls

Rejection Sampling is efficient only when the proposal closely covers the target.
Sampling from the wrong distribution can make the estimate look precise but biased.
Using biased random choices or forgetting to store the seed for reproducible runs.
Handle empty, invalid, and boundary inputs before trusting accepted samples.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show candidate points under a curve being accepted or rejected.

Step 1 of 5: Draw a candidate from the proposal distribution

accept-reject

Notes

Rejection Sampling operates in O(k / a) time and O(k) space within the Sampling family. Key governing relation: accept if u <= target(x) / (M * proposal(x)). Often compared with Importance Sampling and Inverse Transform Sampling.