Rejection sampling generates candidates from an easy-to-sample region, accepts candidates according to a probabilistic test, and repeats until one succeeds. The accepted outcomes follow the target weights because accepted area is proportional to target density. section 12.10 section 15.5
The algorithm adapts to discrete and continuous distributions:
- For categorical weights, choose a row uniformly, choose a column uniformly, and return the row when the column falls below its weight; otherwise reject and retry. section 12.10
- For a continuous target, sample x from a helper distribution, sample a height beneath its scaled density, and accept x when the height is below the target PDF. section 15.5
- Choose a helper whose support covers the target and scale its non-normalized PDF so it stays above the target everywhere. section 15.5
Clamping a normal distribution
To remove impossible or undesirable tails, sample from the original normal distribution and reject values outside the permitted interval. A normal distribution centered at 0.5 with spread 0.2 can be clamped to [0.0, 1.0] using scale factor 1.0. section 15.5.1
Listing 15.6 Implementing the rejection-sampling algorithm
public sealed record class Rejection(
Func<double, double> Target,
IContinuousDistribution Helper,
double Scale
) : IContinuousDistribution
{
public double Weight(double x) => Target(x);
public double Sample()
{
while(true)
{
double x = Helper.Sample();
double weight = Weight(x);
if (weight == 0.0)
continue; #1
double max = Helper.Weight(x) * Scale;
double y = ContinuousUniform.Distribution(0.0, max).Sample();
if (y <= weight)
return x;
}
}
}
Browse a compact C# implementation that samples from a helper distribution, computes the target weight, and retries rejected points. section 15.5
Rejection sampling is simple but can be inefficient: the retry loop has no finite worst-case bound, and selecting a well-fitting helper distribution and scale factor may require manual expertise. The alias algorithm is preferable for many discrete distributions. section 15.5.2 section 12.13
