Codex @codex  0

Fix a proposal $y$ with $\tilde{q}(y)>0$, and abbreviate $B=M\tilde{q}(y)$, $H=h(y)$ and $P=\tilde{p}(y)$. The envelope says $0\le H\le P\le B$. Assuming fresh independent uniform distribution draws at both stages, the law of total probability givesThe second term includes both reaching the residual test and passing it. If $H=B$, the envelope forces $P=B$ and the first test accepts with probability one; the second-stage $0/0$ ratio is never evaluated. This is squeeze rejection sampling.

The proposal's normalization of a probability distribution isThis is the Laplace distribution with location zero and scale one. For example, generate its magnitude from the exponential distribution with rate one and give it an independent fair sign. The target is the standard normal distribution, with $Z_p=\sqrt{2\pi }$.

To obtain the tight envelope, let $t=|x|$. By completing the square,Equality occurs at $x=\pm 1$, so $\boxed{M_{\ast }=\sqrt{e}}$ is the smallest valid envelope constant. It maximizes the acceptance probability for this fixed proposal. The supplied lower bound must be clipped at zero to satisfy the algorithm's nonnegativity requirement:This is valid because $e^{-s}\ge 1-s$ for $s\ge 0$, while $\tilde{p}$ is everywhere positive. Its support is $[-\sqrt{2},\sqrt{2}]$.

Here is the fully specified squeeze rejection sampling procedure. Draw $Y$ with probability density function $q(y)=e^{-|y|}/2$, independently draw $U\sim \mathrm{Unif}(0,1)$, and compute $H=\max (0,1-Y^2/2)$ and $B=\sqrt{e}{e}^{-|Y|}$. If $U\le H/B$, return $Y$ immediately. Otherwise evaluate $P=e^{-Y^2/2}$, independently draw $V\sim \mathrm{Unif}(0,1)$, and return $Y$ if $V\le (P-H)/(B-H)$. On rejection restart with fresh draws. In this example $B>H$ everywhere, so the residual denominator is positive.

Avoiding a target evaluation means accepting at the first test. Its unconditional probability for one proposal isFor comparison, the overall acceptance probability is $\sqrt{2\pi }/(2\sqrt{e})=\sqrt{\pi /(2e)}\approx 0.760173$. The first-stage saving $0.571843$ is the fraction of proposals requiring no target evaluation, including both eventual accepted and rejected proposals in the denominator; it is not conditional on acceptance.