Rejection Sampling

How Rejection Sampling Works

Rejection sampling is a simple fairness-preserving transformation. A generator produces raw values, but any value that would skew the target distribution is rejected and the process repeats until an acceptable value is obtained. The key property is that the accepted result is uniform over the intended range, not merely “close enough”.

This matters because the method is doing distribution shaping, not just value selection. If the underlying source is not aligned to the target range, a naive mapping step can leak bias into anything that depends on the output. Rejection sampling removes that bias by separating “candidate generation” from “acceptance”.

Why Naive Modulo Reduction Is Unsafe

The classic failure mode is modulo bias. When a random number is reduced with a remainder operation, some outputs occur more often than others unless the source range divides evenly into the target range. That creates a measurable skew, which is unacceptable for passwords, tokens, lottery-style selections, shuffles, and other uses that rely on uniformity.

Rejection sampling avoids that problem by discarding candidates in the “extra” portion of the source range, rather than forcing them into the target range. In practice, that means the generator may need more than one draw, but every accepted value carries the same probability within the range.

For security-sensitive generation, this is the difference between a truly uniform output space and one with uneven probabilities that an attacker may exploit or that may weaken entropy assumptions.

Where Rejection Sampling Is Used

The method appears anywhere a system needs an unbiased subset of random values from a larger domain. Common examples include secure token generation, password policy enforcement, randomized selection logic, cryptographic sampling steps, and any code that must avoid bias when converting from one numeric range to another.

Its value is greatest when the output must be both fair and unpredictable. That combination matters in security tooling because even a small bias can become relevant at scale, especially when outputs are used repeatedly or observed over time.

Rejection sampling is usually a low-level implementation detail, but it has high leverage: if the mapping step is wrong, the entire downstream use of the random value inherits the defect.

Trade-offs and Implementation Cautions

The main trade-off is efficiency. Because some values are rejected, the process can require extra iterations, especially when the source range and target range are poorly matched. That overhead is usually acceptable when correctness matters more than raw speed, but it should still be accounted for in performance-sensitive systems.

Another caution is implementation correctness. The acceptance threshold must be calculated carefully, and the raw random source must itself be suitable for the security context. Rejection sampling can preserve uniformity, but it cannot fix a weak or predictable source of randomness.

When implemented correctly, the method is a practical way to preserve fairness without introducing hidden probability shifts into security-critical output.

Risk and Threat Considerations

Bias in random selection is a security problem when the output influences secrets, identifiers, or fairness-sensitive decisions. If a generator systematically favours some results over others, attackers may gain a small but real advantage in guessing, enumeration, or statistical prediction.

Failure mechanism: A naive conversion step, especially modulo reduction, compresses a larger random domain into a smaller one unevenly. That skews the distribution and can make some tokens, passwords, or sampled outcomes more likely than others.

Impact: The result is reduced entropy quality, weaker unpredictability, and a larger attack surface for brute force, correlation, or exploitation of biased selection logic.

Practitioner Guidance

Why practitioners should care: Rejection sampling is the safest default when a random source must be mapped into a smaller range without bias. It is especially important in security code paths where “almost uniform” is not good enough.

What to watch for: Any code that converts random bytes or integers into bounded values deserves review, because shortcut arithmetic often introduces subtle skew. The implementation should be checked for both correctness of the acceptance threshold and suitability of the underlying random source.

Practitioner takeaway: Use rejection sampling whenever the exact distribution matters, and treat any simpler range-reduction shortcut as suspect until proven unbiased.

Related resources from NHI Mgmt Group

• How should internal audit teams reduce reliance on manual sampling in multi-ERP environments?
• What do organisations get wrong about sampling-based data discovery?
• When does telemetry sampling create more risk than it reduces?
• Who should own changes to sampling and routing rules in telemetry pipelines?