Rejection sampling

For each integer $m\ge 1$, define $s_m(n)=\min \{f(n),m\}$ when $n<m$ and $s_m(n)=0$ when $n\ge m$. Every subset of $\mathbb{N}$ is measurable under [F1], so $s_m$ is measurable; its range is finite, hence it is simple by [F2]. For fixed $n$, the indicator $1_{n<m}$ is eventually one; if $f(n)<+\mathrm{\infty }$, [F5] ensures the increasing canonical naturals eventually exceed $f(n)$, while if $f(n)=+\mathrm{\infty }$ the capped values increase without bound. Thus $s_m(n)\uparrow f(n)$ for every $n$. Monotone convergence [F3] gives $\int fd\mathrm{\#}={\lim }_{m\to \mathrm{\infty }}\int s_{m}d\mathrm{\#}$.

By [F1] and [F2], for every $m\ge 1$, $\int s_{m}d\mathrm{\#}={\sum }_{n<m}\min \{f(n),m\}\mathrm{\#}(\{n\})={\sum }_{n<m}\min \{f(n),m\}=:D_m\mathrm{.}$ For each $n<m$, $\min \{f(n),m\}\le \min \{f(n),m+1\}$ and $D_{m+1}$ adds a nonnegative term, so $D_m$ is nondecreasing. Termwise $\min \{f(n),m\}\le f(n)$, so $D_m\le P_m\le {\sum }_{n=0}^{\mathrm{\infty }}f(n)$ by [F4].

Fix $r\ge 0$. If $P_r=+\mathrm{\infty }$, some $f(n)=+\mathrm{\infty }$ with $n<r$, so for every $m\ge r$ with $m>n$, $D_m\ge m$; the canonical naturals are unbounded by [F5], hence ${\lim }_m{D}_m=+\mathrm{\infty }\ge P_r$. If $P_r<+\mathrm{\infty }$, then each $f(n)$ for $n<r$ is finite. Write $\bar{r}=r\cdot 1_{\mathbb{R}}$ and apply [F5] to $P_r+\bar{r}$ to choose an integer $m$ with $m\cdot 1_{\mathbb{R}}>P_r+\bar{r}$. Then $m\ge r$ and $m>f(n)$ for every $n<r$, since nonnegative summands give $f(n)\le P_r$. Thus $D_m\ge P_r$, and monotonicity of $D_m$ again gives ${\lim }_m{D}_m\ge P_r$. Since this holds for every $r$, [F4] implies ${\lim }_m{D}_m\ge {\sum }_{n=0}^{\mathrm{\infty }}f(n)$. Together with step 2.1's reverse bound, ${\lim }_m{D}_m={\sum }_{n=0}^{\mathrm{\infty }}f(n)$.

Steps 1.1 and 2.1 identify the integral with ${\lim }_m{D}_m$, and step 3.1 identifies that limit with the nonnegative extended series. This proves the stated identity, including infinite values.

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.

Let $A_i$ be the event that proposal $i$ is accepted. The algorithm uses the same measurable acceptance region for each IID proposal-uniform pair, so mutual independence and common distribution in [F1] imply that the events $A_i$ are IID. By [F2], $\mathbb{P}(A_i)=p$ for every $i$. Therefore $\mathbb{P}(N>m)=q^m$ for $m\ge 0$, and $\mathbb{P}(N=k)=\mathbb{P}(A_1^c\cap \cdots \cap A_{k-1}^c\cap A_k)=q^{k-1}p$ for each $k\ge 1$.

For each $m\ge 1$, the pointwise identity $N\wedge m={\sum }_{j=1}^m{\mathbf{1}}_{\{N\ge j\}}$ holds, including on the null event $N=\mathrm{\infty }$. By [F3], [F4], and step 1.1, $\mathbb{E}[N\wedge m]={\sum }_{j=1}^m\mathbb{P}(N\ge j)={\sum }_{j=0}^{m-1}{q}^j\mathrm{.}$

The truncations $N\wedge m$ increase pointwise to $N$. By [F5] and then [F6], $\mathbb{E}[N]={\lim }_{m\to \mathrm{\infty }}\mathbb{E}[N\wedge m]={\sum }_{j=0}^{\mathrm{\infty }}{q}^j=\frac{1}{1-q}=\frac{1}{p}\mathrm{.}$ This is finite because $p>0$.

Substituting $p=Z_f\mathrm{/}(c{Z}_g)$ from [F2] gives $\mathbb{E}[N]=c{Z}_g\mathrm{/}{Z}_f$; when $Z_f=Z_g=1$, this is $c$.