Rejection Sampling: How Discarding Values Can Preserve Fairness

Rejection sampling creates a desired distribution by proposing values and accepting them according to a rule. In simple integer generation, it can remove an uneven surplus so every final outcome has exactly the same number of accepted source values. Discarding a proposal is not inherently biased; what matters is the acceptance rule.

A bag-of-tickets explanation Imagine 256 equally likely tickets, labelled 0–255, assigned cyclically to six outcomes. Four outcomes have one extra ticket. Remove those four surplus tickets before accepting a proposal, and each outcome is represented equally.

The general rule is L = floor(M/m) × m for source size M and target size m. Accept x < L, then return x mod m. The acceptance probability is L/M, and the expected proposals per accepted value are M/L. These are properties of the construction, not estimates from a frequency chart.

Rejection can also enforce distinctness Suppose a 6/49 generator samples a label uniformly from 1–49. If the label has already been selected for the current line, it samples again. At a stage where j distinct labels have been selected, every unselected label has the same proposal probability and the same acceptance condition. Conditional on acceptance, each remaining label is therefore equally likely.

The probability of acceptance at that stage is (49−j)/49. The expected number of proposals to obtain six distinct labels is the sum of 49/(49−j) for j = 0 through 5. It is a little more than six. For a small selection from a much larger pool, this is efficient.

When efficiency becomes a problem If you try to select nearly every label by repeatedly rejecting duplicates, most late proposals will already be present. A partial Fisher–Yates shuffle can be more efficient: choose uniformly from the remaining positions, swap the chosen item into the selected segment, and continue.

The two methods can produce the same uniform distribution of subsets while using different amounts of work. “Same distribution” does not mean they produce the same sequence for a given seed, because they consume random values differently.

The acceptance rule must match the goal Rejecting duplicate labels enforces a game's distinctness rule. Rejecting every line with consecutive numbers does something else: it removes valid combinations because of their appearance. That creates a conditional distribution over the lines that pass the filter, rather than a uniform distribution over all valid lines.

A filter is not necessarily wrong if its purpose is disclosed. It is wrong to describe the filtered output as an unrestricted uniform sample from the original space. That distinction applies to balanced odd/even filters, preferred sums and birthday exclusions as well.

How to verify the implementation Use a tiny pool for which every subset can be enumerated. Check invalid inputs, boundaries, duplicate rules and separate pools. Then compare the intended probability model with the algorithm's reasoning. Statistical tests can reveal problems, but they cannot rescue an incorrect proof of fairness.

The Lab's die example makes rejection visible with a small source range. Its lottery simulation uses rejection of within-row duplicates and publishes the full procedure. Both are examples of matching an acceptance rule to a precisely stated sample space.