= Squeeze rejection sampling
{title2=$0\leq h\leq\widetilde p\leq M\widetilde q$}
A lower envelope $h$ can save evaluations of an expensive unnormalized target $\widetilde p$ in <rejection sampling>. Draw $Y$ with <probability density function> $\widetilde q/Z_q$ and an <independent> <uniform distribution> value $U$. Accept immediately if $U\leq h(Y)/(M\widetilde q(Y))$. Otherwise draw a fresh <independent> <uniform distribution> value $V$ and accept if
$$
V\leq\frac{\widetilde p(Y)-h(Y)}{M\widetilde q(Y)-h(Y)}.
$$
For a fixed proposal, writing $B=M\widetilde q(Y)$, $H=h(Y)$ and $P=\widetilde p(Y)$ gives total acceptance <probability> $H/B+(1-H/B)(P-H)/(B-H)=P/B$. If $H=B$, the first stage accepts with <probability> one and the residual test is skipped. Thus the accepted <probability density function> is $\widetilde p/Z_p$, and the overall acceptance <probability> is $Z_p/(MZ_q)$. The <probability> of avoiding a target evaluation on one proposal is $\int h/(MZ_q)$.
Back to article page
