Rejection sampling
= Rejection sampling
{wiki}
= Rejection method
{synonym}
Suppose $f$ is a target probability density and $h$ is a proposal density with $f(x)\leq Mh(x)$. Draw $X\sim h$ and an independent $U\sim\operatorname{Uniform}[0,1]$, and accept $X$ when
$$
U\leq\frac{f(X)}{Mh(X)}.
$$
The accepted value has density $f$, the acceptance probability is $1/M$, and the expected number of proposals is $M$.