Rejection Sampling Problems
2 Rejection Sampling LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Discard outcomes that would introduce bias
Rejection sampling starts from outcomes that are easy to generate uniformly and accepts only a suitable subset. To implement rand10 using rand7, two independent rand7 calls give 49 equally likely pairs. Because 49 is not divisible by 10, mapping every pair with modulo would favor some outputs.
When to use it
Use rejection when a proposal space contains a uniformly usable region. For a random point in a circle, proposing uniformly in its bounding square and rejecting points outside the disk preserves uniform area density inside the circle.
Worked example
Let a and b be independent uniform integers from 1 through 7.
- Compute x = 7 × (a - 1) + (b - 1). Each integer from 0 through 48 occurs with probability 1/49.
- Accept x < 40. Otherwise discard the pair and generate a fresh pair.
- For an accepted x, return 1 + (x mod 10). Each output has exactly four accepted preimages.
Every result from 1 to 10 has probability 1/10. A single attempt is accepted with probability 40/49.
Time and space
For this basic method, the expected number of attempts is 49/40, so the expected number of rand7 calls is 49/20 = 2.45. Auxiliary space is O(1). There is no finite worst-case bound on retries, although termination occurs with probability 1.
Mistakes to check
- Using 1 + (x mod 10) on all 49 values is biased: some outputs have five preimages and others only four.
- Each retry needs fresh independent randomness. Reusing part of a rejected pair requires a separate proof of the resulting distribution.
- A radius chosen uniformly from 0 to R does not produce a point uniform by area in a disk; there is more area near the boundary.
Further reading: LeetCode: Implement Rand10 Using Rand7 contract
Guide reviewed .