Rejection sampling has the target acceptance law

By [F3], both shapes are finite outside null sets. Let $E_0$ be the measurable null union of those sets and the envelope exception from [A1]. For any nonnegative measurable $h$ supported on $E_0$, every simple minorant has all its positive level sets contained in $E_0$, so its simple integral is zero; hence $\int hd\mu =0$ by [F4]. For either shape $h$ and any measurable $A$, the decomposition $h{\mathbf{1}}_A=h{\mathbf{1}}_{A\setminus E_0}+h{\mathbf{1}}_{A\cap E_0}$ and additivity [F4] therefore give ${\int }_{A}hd\mu ={\int }_{A}h{\mathbf{1}}_{S\setminus E_0}d\mu$. Products here use $0\cdot \mathrm{\infty }=0$, and are measurable by [F9]. Replace each shape by $h{\mathbf{1}}_{S\setminus E_0}$; neither density measure nor any displayed integral changes. In particular $G(E_0)=0$. By [F13] and countable additivity [F11], the probability that any proposal hits $E_0$ is zero; changing the acceptance rule there leaves the output law unchanged. The new shapes are finite and satisfy $\tilde{f}\le c\tilde{g}$ everywhere, so $\tilde{g}=0$ implies $\tilde{f}=0$.

Fix $A\in \mathcal{S}$ and let $Q(A):=\mathbb{P}(Y_1\in A,U_1\le a(Y_1))$. By [F9] the event is measurable. By [F1] and [F6] the joint law of $(Y_1,U_1)$ is $G\otimes \mathrm{\Lambda }$. Hence [F5] and [F13] give $Q(A)={\int }_{S\times (0,1)}{\mathbf{1}}_A(y){\mathbf{1}}_{\{u\le a(y)\}}(G\otimes \mathrm{\Lambda })(d(y,u))\mathrm{.}$

Tonelli [F7] evaluates the last integral as $Q(A)={\int }_A\mathrm{\Lambda }((0,a(y)])G(dy)={\int }_{A}a(y)G(dy),$ including $a(y)=0$ and $a(y)=1$, since $\mathrm{\Lambda }((0,t])=t$ on $[0,1]$.

Apply [F8] to the proposal density $\tilde{g}\mathrm{/}{Z}_g$ and the measurable function ${\mathbf{1}}_{A}a$. Where $\tilde{g}>0$, the envelope makes $a=\tilde{f}\mathrm{/}(c\tilde{g})$; where $\tilde{g}=0$, [step 1.1] gives $\tilde{f}=0$. Therefore $Q(A)=\frac{1}{Z_g}{\int }_{A}a\tilde{g}d\mu =\frac{1}{c{Z}_g}{\int }_A\tilde{f}d\mu \mathrm{.}$

Taking $A=S$ in step 3.1 gives $p=Q(S)=Z_f\mathrm{/}(c{Z}_g)>0$. Integrating the pointwise envelope and using [F10] gives $Z_f\le c{Z}_g$, so $p\le 1$. For normalized densities, $Z_f=Z_g=1$, hence $p=1\mathrm{/}c$ and $c\ge 1$.

Put $q=1-p$. Independence of the proposal-uniform pairs [F1] gives $\mathbb{P}(N>m)=q^m$ for every $m\ge 1$. Since $0\le q<1$, [F12] gives $q^m\to 0$; the event $\{N=\mathrm{\infty }\}$ is contained in every $\{N>m\}$, so $\mathbb{P}(N=\mathrm{\infty })=0$.

For each $k\ge 1$, independence across trials gives $\mathbb{P}(N=k,Y_k\in A)=q^{k-1}Q(A)\mathrm{.}$ These events are disjoint, so countable additivity [F11] and the geometric series [F12] yield $\mathbb{P}(\text{the algorithm outputs a value in }A)={\sum }_{k=1}^{\mathrm{\infty }}{q}^{k-1}Q(A)=\frac{Q(A)}{p}=\frac{1}{Z_f}{\int }_A\tilde{f}d\mu \mathrm{.}$ The almost-sure termination in step 5.1 makes this the full output law.