Rejection sampling

Let $(S,\mathcal{S},\mu )$ be a measure space. The nonnegative measurable functions $\tilde{f},\tilde{g}:S\to [0,\mathrm{\infty })$ are the target and proposal shapes, with $Z_f:={\int }_S\tilde{f}d\mu \in (0,\mathrm{\infty }),Z_g:={\int }_S\tilde{g}d\mu \in (0,\mathrm{\infty })\mathrm{.}$ The normalized densities $\bar{f}:=\tilde{f}\mathrm{/}{Z}_f$ and $\bar{g}:=\tilde{g}\mathrm{/}{Z}_g$ are measurable by closure under scalar multiplication (Arithmetic and lattice operations preserve measurability whenever they are defined). Their integrals are one by homogeneity of the nonnegative integral (Monotonicity and nonnegative homogeneity of the nonnegative integral). Thus their density measures are probability laws by The measure with density $f$ relative to $\mu$ and Probability measures and probability spaces: $F(A):=Z_f^{-1}{\int }_A\tilde{f}d\mu ,G(A):=Z_g^{-1}{\int }_A\tilde{g}d\mu (A\in \mathcal{S})\mathrm{.}$ Assume a finite $c>0$ satisfies $\tilde{f}\le c\tilde{g}$ outside a common $\mu$-null set. Use finite-valued representatives; values on that null set do not affect $F$ or $G$.

The stochastic input is an ideal sequence of independent proposal draws $Y_i$ with common law $G$ and independent auxiliary draws $U_i$ with common law $\mathrm{\Lambda }$, where $\mathrm{\Lambda }$ is the uniform probability law on $(0,1)$: $\mathrm{\Lambda }(U\le t)=t$ for $0\le t\le 1$. The two sequences are independent, so the pairs $(Y_i,U_i)$ are IID in the sense of Identical distribution and IID families. This contract assumes exact draws; it makes no claim about a finite-precision pseudorandom generator.

Define the measurable acceptance function $a(y):=\{\begin{array}{ll}0,& \tilde{g}(y)=0,\\ \min \text{\hspace{0.17em}⁣}\{1,{\displaystyle \frac{\tilde{f}(y)}{c\tilde{g}(y)}}\},& \tilde{g}(y)>0.\end{array}$ It is measurable. The reciprocal extension $h:[0,\mathrm{\infty })\to [0,\mathrm{\infty })$, $h(t)=1\mathrm{/}t$ for $t>0$ and $h(0)=0$, is Borel: for every real $r$, its strict upper level set is $[0,\mathrm{\infty })$ if $r<0$, $(0,\mathrm{\infty })$ if $r=0$, and $(0,1\mathrm{/}r)$ if $r>0$. These are Borel sets in the subspace $[0,\mathrm{\infty })$ by The Borel sigma-algebra of a topological space, so the threshold characterization Threshold characterisations of real-valued and extended-real-valued measurability applies. Equivalently, $a(y)=\min \{1,\tilde{f}(y)h(\tilde{g}(y))\mathrm{/}c\}$. Arithmetic operations and Borel composition preserve measurability by Arithmetic and lattice operations preserve measurability whenever they are defined and Composition with a Borel measurable outer map preserves measurability. Where the envelope holds and $\tilde{g}(y)>0$, this is exactly $\tilde{f}(y)\mathrm{/}(c\tilde{g}(y))$; where $\tilde{g}(y)=0$, $a(y)=0$. At an exceptional point with $\tilde{g}(y)>0$ where the quotient exceeds $1$, replacing it by $1$ does not change the test $U_i\le \tilde{f}(y)\mathrm{/}(c\tilde{g}(y))$, since $U_i\in (0,1)$.

Procedure. For $i=1,2,\dots$, draw $(Y_i,U_i)$. If $U_i\le a(Y_i)$, return $Y_i$ and stop; otherwise continue to the next pair. When $\tilde{f}=f$ and $\tilde{g}=g$ are normalized densities, integrating $f\le cg$ gives $c\ge 1$, and the rule is the usual threshold $f(Y_i)\mathrm{/}(cg(Y_i))$.