Rejection Sampling

Rejection Sampling generates samples that are exactly distributed as the target $p(x)$ when direct sampling is hard: pick an easy-to-sample proposal $q(x)$ and a constant $M$ with $p(x) \le M q(x)$ for all $x$ (envelope condition). Loop: draw $X \sim q$, then $U \sim \text{Uniform}(0, 1)$; accept $X$ if $U \le p(X)/(M q(X))$, otherwise retry. Acceptance probability:

where $q(x)$ is the density of $X$ at $x$ and the factor in parentheses is the conditional acceptance probability at $x$; the expected number of trials is exactly $M$ — tighter envelopes ($M$ close to 1) are more efficient, and the result is independent of the normalization constant of $p$ (any constant factor is absorbed into the envelope).

targets known only up to a constant (e.g. Bayesian posteriors $\propto$ prior $\times$ likelihood) in low dimension; interviews often ask for the acceptance-rate derivation and "why it fails in high dimensions".

exact samples without inverting a CDF or normalizing the target — the simplest general exact sampler; but the acceptance rate $1/M$ decays exponentially with dimension $d$ ($M \propto c^d$) because of volume concentration, so nearly all proposals are rejected and one must switch to MCMC or importance sampling.

Derive the acceptance probability $P(\text{accept}) = 1/M$; why is it independent of the normalization constant of $p$?

Full algorithm of rejection sampling? How does the expected number of trials relate to $M$?

Why does rejection sampling fail in high dimensions (volume concentration, exponentially growing envelope)?

How to choose a good proposal $q$ and constant $M$? What does a loose envelope cost?

Can rejection sampling handle unnormalized $p$? How is the constant factor absorbed?