 Squeeze rejection sampling

A lower envelope $h$ can save evaluations of an expensive unnormalized target $\tilde{p}$ in rejection sampling. Draw $Y$ with probability density function $\tilde{q}/Z_q$ and an independent uniform distribution value $U$. Accept immediately if $U\le h(Y)/(M\tilde{q}(Y))$. Otherwise draw a fresh independent uniform distribution value $V$ and accept ifFor a fixed proposal, writing $B=M\tilde{q}(Y)$, $H=h(Y)$ and $P=\tilde{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 $\tilde{p}/Z_p$, and the overall acceptance probability is $Z_p/(M{Z}_q)$. The probability of avoiding a target evaluation on one proposal is $\int h/(M{Z}_q)$.