Rejection Sampling

Type: Math / Theory LeetCode tag size: < 50 problems — define the concept, core algorithms, and when it applies.

---

Core Concepts

Rejection sampling — a method for generating samples from a target distribution B using a sampler for an easier source distribution A, by accepting or rejecting each draw from A based on a probability proportional to how well it matches B. Accepted samples follow B exactly, without bias.

Acceptance criterion — a sample x drawn from A is accepted with probability P_B(x) / (c · P_A(x)), where c is a constant chosen so that c · P_A(x) ≥ P_B(x) for all x. The constant c equals max P_B(x) / P_A(x) and is called the envelope constant.

Expected number of trials — the expected number of draws from A before one accepted sample equals c. Lower c → more efficient sampler. Choosing the tightest possible envelope minimises iterations.

Uniform source — in most LeetCode problems, A is a uniform integer or uniform continuous distribution. The acceptance rule then simplifies to: accept x only if it falls within a sub-range that maps uniformly to the target range.

Valid sub-range — for integer problems, find the largest multiple of the target range size that fits within the source range; reject all draws above that multiple. This ensures the usable portion of the source is itself uniformly distributed over the target.

Combined range construction — when a single uniform draw cannot cover the target, combine two or more independent draws to construct a uniform draw over a larger range. If source is Rand_b (uniform 1..b), then (r1 − 1) * b + r2 is uniform over [1, b²]. Generalises to k draws giving range b^k.

Polar coordinate method — an alternative to rejection sampling for continuous uniform sampling inside a disc. Sample radius as r = R * sqrt(uniform()) and angle as θ = 2π * uniform(). Avoids rejection entirely but requires knowing the geometry.

---

Types / Variants

---

Key Algorithms

Integer RNG Transformation via Rejection

Transforms Rand_a (uniform integer in [1, a]) into Rand_b (uniform integer in [1, b]) where b > a.

Key insight: combine k independent calls to construct a uniform draw over [1, a^k]. Identify the largest multiple of b that fits within a^k — call it M = floor(a^k / b) * b. Reject values above M; return (accepted_value - 1) % b + 1.

while True:
    val = (rand_a() - 1) * a + rand_a()  # uniform in [1, a²]
    if val <= (a * a // b) * b:
        return (val - 1) % b + 1

Time: O(c) expected, where c = a² / M ≤ a²/(a²−b+1); Space O(1). The expected iterations stay constant regardless of how many samples are drawn.

Random Point in a Circle via Rejection

Generate a point (x, y) uniformly distributed inside a circle of radius R centred at (x0, y0).

Key insight: sample uniformly in the bounding square [−R, R] × [−R, R]; reject if x² + y² > R². Accepted points are uniform inside the disc because the rejection rule is the exact indicator of membership.

while True:
    x, y = random.uniform(-r, r), random.uniform(-r, r)
    if x*x + y*y <= r*r:
        return [x0 + x, y0 + y]

Time: O(1) expected (acceptance probability = π/4 ≈ 0.785); Space O(1).

Random Point in a Circle via Polar Coordinates

Generate the same uniform disc distribution without rejection.

Key insight: area in a disc scales as r², so to get uniform area density, the CDF of r is F(r) = r²/R². Inverting: sample r = R · sqrt(uniform()). Sample θ = 2π · uniform().

r = radius * math.sqrt(random.random())
theta = 2 * math.pi * random.random()
return [x_center + r * math.cos(theta), y_center + r * math.sin(theta)]

Time O(1), Space O(1). Preferred over rejection when avoiding looping matters (e.g., deterministic runtime required).

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Naive radius sampling: using r = random() * R instead of r = sqrt(random()) * R for a disc concentrates samples near the centre, because area scales as r² and a linear draw over radius over-represents small radii.

• Off-by-one in usable multiple: the rejection boundary is (source_range // target) * target. Including target extra values (using a loose boundary) makes some outcomes appear twice as often. Excluding valid values (using a tight boundary minus 1) introduces bias in the other direction. The formula above is exact.

• Combining more draws than necessary: using three calls when two suffice wastes expected calls. Always check whether a² ≥ b before trying a³.

• Source range not large enough for any multiple: if b > a², you need k draws such that a^k ≥ b. For most LeetCode problems this is k = 2, but verify before coding.

• Integer overflow in combined range: (r1 - 1) * a + r2 can overflow 32-bit int if a is large. In Python this is never an issue, but note it if porting to Java/C++.

• Returning val % b instead of (val-1) % b + 1: if the source is 1-indexed, a direct % b maps value b to 0 rather than b, producing a distribution over [0, b−1] with 0 and b each appearing once instead of a uniform [1, b].

• Rejection loop never terminating in theory: while the expected number of iterations is finite, there is no hard upper bound. In an interview, acknowledge this and state the expected constant.

---

Implementation Notes

• Python random.random() returns [0.0, 1.0) — use this for polar angle and radius CDF inversion.
• Python random.uniform(a, b) is equivalent to a + (b-a) * random.random() — use for bounding-box sampling.
• The while True loop pattern with an internal return is idiomatic for rejection sampling in Python; no sentinel value is needed.
• For the combined-range trick, the result before rejection is (r1 - 1) * base + r2, which is 1-indexed; subtract 1 before % target, then add 1 to restore 1-indexing.
• math.sqrt and math.cos/math.sin introduce floating-point error; this is acceptable for all LeetCode problems in this tag, which use float tolerances of 1e-5.

---

Cross-Topic Relations

See probability-and-statistics.md for Fisher-Yates shuffle, reservoir sampling, and weighted random pick — techniques often grouped with rejection sampling on LeetCode.

---

Interview Reference

Must-Know Problems

Integer RNG Transformation

• Implement Rand10() Using Rand7() (470) — canonical example; derive combined range [1, 49], usable multiple 40, map to [1, 10]

Geometric Uniform Sampling

• Generate Random Point in a Circle (478) — implement both rejection (bounding square) and polar methods; know the r = R√u insight
• Random Point in Non-overlapping Rectangles (497) — weight rectangles by area, pick rectangle, then sample uniformly inside; no rejection needed but same probability tag

Clarification Questions to Ask

• Is the source RNG 0-indexed or 1-indexed? (affects the (r1-1)*base + r2 formula)
• Is the radius/boundary inclusive? (affects the <= vs < in the rejection check)
• Is a deterministic runtime required, or is expected O(1) acceptable? (rejection has probabilistic runtime; polar method is deterministic)
• For integer RNG: what is the exact range of the target? Confirm b is given as [1, b] not [0, b−1].
• Is the answer required as a float, or will an integer grid point suffice?

Common Interview Mistakes

• Sampling r = random() * R for a circle instead of r = sqrt(random()) * R — visually clusters points at the centre; fails any uniformity check.
• Using val % b on a 1-indexed combined range — shifts the output by 1, so outcome b maps to 0.
• Forgetting to reject: implementing the combined range but returning (val - 1) % b + 1 for all values of val including those above the usable multiple — makes lower-indexed outcomes slightly more likely.
• Choosing k = 3 draws when k = 2 suffices, or failing to verify that a^k ≥ b before selecting k.
• Not accounting for the while True loop in runtime analysis — state expected O(c) calls and identify c explicitly.

Typical Follow-Up Escalations

• "What is the expected number of calls to Rand7?" → c = 49 / 40 ≈ 1.225 per output; each call uses 2 Rand7 calls, so expected Rand7 calls = 2 × 49/40 = 2.45.
• "Can you reduce the expected number of calls?" → recycle rejected values: the rejected range [41, 49] has 9 values, uniform in [1, 9]; use these as a head-start on the next pair of Rand7 calls.
• "Implement this without a while loop" → not possible in the pure rejection model; switch to polar coordinates for the circle problem to eliminate looping.
• "What if the circle has a non-zero centre?" → shift the sampled point: return [x_center + x, y_center + y] after sampling from a centred disc.
• "How would you test that your implementation is uniform?" → run N samples, bin them, check that each bin has approximately N / target count; chi-squared test for rigour.