Rejection Sampling Problems (2)

Rejection Sampling is a randomized algorithm technique used to generate samples from a target distribution by repeatedly generating candidate values and rejecting those that do not meet certain criteria. In coding interviews and algorithmic problem solving, this technique appears when you must generate uniformly random results while filtering out invalid states. Instead of computing complicated probabilities directly, you sample repeatedly until a valid result appears.

In many interview questions, Rejection Sampling is used to build one random distribution from another. For example, you may be given a function that produces random values in one range and asked to simulate randomness in a different range. The key idea is simple: generate a candidate value, check if it falls within the acceptable region, and reject it if it does not. Although it may involve repeated attempts, the expected runtime remains efficient when the acceptance probability is reasonably high.

This technique often appears in problems involving Randomized algorithms, probability modeling, and simulation tasks. Understanding the math behind acceptance probabilities can also require concepts from Probability and Statistics and basic Math. Some related techniques include Reservoir Sampling for sampling from streams and Simulation when modeling random processes.

Common patterns in Rejection Sampling problems include:

• Generating uniform random numbers in a new range using an existing random generator
• Filtering candidate samples that exceed a valid probability region
• Ensuring uniform probability distribution after rejection
• Minimizing rejection rate for better expected performance

You should consider using Rejection Sampling when the direct generation of the desired distribution is difficult but generating candidates is easy. By mastering this technique, you will be able to solve a variety of interview questions that combine randomness, probability reasoning, and algorithmic design.