Codex @codex  0

For normal rejection sampling with an exponential envelope, complete the square in the probability density function ratio:The maximum occurs at $x=\lambda$, which lies in the support because $\lambda >0$. ThusThe PDF exponent is $e^{{\lambda }^2}$ inside the square root; this distinction is lost in the converted TeX.

The acceptance rule simplifies toAn exponential proposal can be generated as $Y=-{\lambda }^{-1}\log V$ from an independent uniform distribution value $V$. Since the target is normalized, the overall acceptance probability is $1/M(\lambda )$. To maximize it,Therefore the optimal rate is $\lambda =1$, with acceptance probability $\sqrt{\pi /(2e)}$.

Finally, give each accepted half-normal distribution value $Y$ an independent fair sign $R\in \{-1,1\}$ and output $Z=RY$. On each half-line its probability density function is half the reflected half-normal distribution probability density function:Consequently $Z\sim N(0,1)$. The sign must be drawn independently; rejection itself does not supply it.

Choose a proposal probability density function $g$ and a finite envelope constant $M$ such that $f(y)\le Mg(y)$ wherever the target has positive density. A rejection sampling trial draws $Y\sim g$ and, independently, $U\sim \mathrm{Uniform}(0,1)$; accept $Y$ whenotherwise repeat with fresh independent draws. For any measurable set $D$,In particular $\mathbb{P}(\mathrm{accept})=1/M$, so the conditional accepted density is $f$. More explicitly, summing over the possible first accepted trial givesThus the algorithm terminates almost surely and its output has exactly the requested law.

The envelope constant satisfies $M\ge 1$ and is the expected number of proposal trials for one output, by the geometric distribution of the waiting time. This is the quantity often called the rejection rate $M$. The actual probability of rejecting a particular proposal is $1-1/M$, and the expected number of rejections before one acceptance is $M-1$; these conventions should not be conflated.

To generate a standard normal distribution, first generate its absolute value, whose half-normal distribution density isWith the given exponential distribution proposal, the density ratio isIts maximum is at $y=\lambda$, hence the normal rejection sampling with an exponential envelope constant isDraw $Y\sim \mathrm{Exp}(\lambda )$ and a fresh uniform $U$; accept when $U\le e^{-(Y-\lambda {)}^2/2}$. An accepted $Y$ has density $h$. Independently choose a sign, positive or negative with probability $1/2$, and output $Z$ with that sign and magnitude $Y$. On either half-line its density is $h(|z|)/2=(2\pi {)}^{-1/2}{e}^{-z^2/2}$, proving the normal output law.

To optimize the rejection rate, differentiateIts derivative is $\lambda -1/\lambda$, negative before one and positive after one; equivalently its second derivative is $1+1/{\lambda }^2>0$. ThusThe rejection probability is consequently about $0.23983$.

To use only uniforms, apply inverse transform sampling: for an independent $U_1\in (0,1)$,has survival probability $\mathbb{P}(Y>y)=e^{-\lambda y}$ for $y\ge 0$. Use a second independent uniform for acceptance, and, after acceptance, a third independent uniform to choose the sign. Repeat with fresh uniforms after any rejection. No exponential generator is then needed.