RejectionSampling
Rejection sampling is a basic Monte Carlo method for drawing samples from a target probability distribution by using a simpler, easy-to-sample proposal distribution. It works by generating candidates from the proposal and accepting them with a probability that corrects for the mismatch between the target and the proposal. The target distribution is described by its density π(x) with respect to a common measure, and the proposal distribution has density q(x). A constant M ≥ sup_x (π(x)/q(x)) is required so that π(x) ≤ M q(x) for all x. If the target density is known only up to a normalization constant, one can use an unnormalized f(x) ∝ π(x) and require f(x) ≤ M q(x).
Algorithm: Repeat until a sample is accepted. Draw X from the proposal density q(x). Draw U from
Choice of proposal and efficiency: The efficiency of rejection sampling hinges on how closely q(x) covers π(x)
Limitations and variations: Rejection sampling can be inefficient if M is large or if the target is