Ordinary and self-normalized importance sampling

Use [F5] with density $r=q$ for integration against $Q$ and with $r=\tilde{p}\mathrm{/}{Z}_p$ for integration against $\pi$. For every $i$, apply the nonnegative case of [F2] to $\mathrm{\mid }{Y}_i\mathrm{\mid }$. Since $X_i$ has law $Q$, ${\mathbb{E}}_Q\mathrm{\mid }{Y}_i\mathrm{\mid }={\int }_{\{q>0\}}\frac{\mathrm{\mid }f(x)\mathrm{\mid }\tilde{p}(x)}{Z_{p}q(x)}q(x)d\mu (x)=\frac{1}{Z_p}{\int }_{\{q>0\}}\mathrm{\mid }f\mathrm{\mid }\tilde{p}d\mu \le \frac{1}{Z_p}{\int }_{\mathsf{X}}\mathrm{\mid }f\mathrm{\mid }\tilde{p}d\mu <\mathrm{\infty }\mathrm{.}$ Thus $Y_i$ is $Q$-integrable. For any real measurable $h$ whose absolute integral is finite against $rd\mu$, apply [F5] separately to $h^{+}=\max (h,0)$ and $h^{-}=\max (-h,0)$: both product integrals are finite because $h^{\pm }\le \mathrm{\mid }h\mathrm{\mid }$. Subtracting their finite identities yields $\int hd(rd\mu )=\int hrd\mu$, since $(hr{)}^{\pm }=h^{\pm }r$ for $r\ge 0$ (with the density convention $0\cdot \mathrm{\infty }=0$). The integrable case of [F2] therefore gives ${\mathbb{E}}_Q[Y_i]={\int }_{\{q>0\}}\frac{f(x)\tilde{p}(x)}{Z_{p}q(x)}q(x)d\mu (x)=\frac{1}{Z_p}{\int }_{\{q>0\}}f\tilde{p}d\mu \mathrm{.}$ The support condition makes $f\tilde{p}=0$ $\mu$-almost everywhere on $\{q=0\}$; hence this last integral equals $Z_p^{-1}{\int }_{\mathsf{X}}f\tilde{p}d\mu =\int fd\pi =\theta$.

By [F1], ${\widehat{\mu }}_{\mathrm{I}\mathrm{S}}=n^{-1}{\sum }_{i=1}^n{Y}_i$. Apply [F3] and step 1.1 to obtain ${\mathbb{E}}_Q[{\widehat{\mu }}_{\mathrm{I}\mathrm{S}}]=n^{-1}{\sum }_{i=1}^n{\mathbb{E}}_Q[Y_i]=\theta$.

By [F1], each $Y_i$ is obtained from $X_i$ by the same measurable weighted-integrand map and ${\widehat{\mu }}_{\mathrm{I}\mathrm{S}}=n^{-1}{\sum }_{i=1}^n{Y}_i$. Since the $X_i$ are IID, [F3] preserves independence and their common law under this map; [F4] therefore makes $(Y_i)$ IID.

Applying [F2] to a sample of size one gives ${\mathbb{E}}_Q{Y}_1=\theta$, and it also gives ${\mathbb{E}}_Q[{\widehat{\mu }}_{\mathrm{I}\mathrm{S}}]=\theta$ for the supplied sample. By step 1.1 every $Y_i$ has the same finite second moment and variance ${\sigma }^2$, and the finite family is pairwise independent. Thus [F5] gives ${\mathrm{Var}}_Q({\sum }_{i=1}^n{Y}_i)=n{\sigma }^2$ and ${\mathrm{Var}}_Q({\widehat{\mu }}_{\mathrm{I}\mathrm{S}})=n^{-2}(n{\sigma }^2)={\sigma }^2\mathrm{/}n$.

Use [F11] with density $r=q$ for integration against $Q$. Applying [F6] to the nonnegative squared weighted integrand gives ${\mathbb{E}}_Q[Y_1^2]=Z_p^{-2}{\int }_{\{q>0\}}f(x{)}^2\tilde{p}(x{)}^2\mathrm{/}q(x)d\mu (x)$. By [F5] and step 2.1, ${\sigma }^2={\mathbb{E}}_Q[Y_1^2]-{\theta }^2$, proving the displayed variance formula.

For the CLT, use the given IID sequence $(X_i{)}_{i\ge 1}$ and assume AC as in [A1]. The measurable transformation in step 1.1 now makes $(Y_i{)}_{i\ge 1}$ IID. If ${\sigma }^2>0$, [F8] applies to the IID sequence from step 1.1 with mean $\theta$ from step 2.1 and yields the stated normal limit. If ${\sigma }^2=0$, [F7] gives ${\mathbb{E}}_Q[(Y_1-\theta {)}^2]=0$, so [F9] implies $Y_1=\theta$ $Q$-almost surely. By the common-law conclusion of step 1.1, each event $\{Y_i\mathrm{\ne }\theta \}$ is null; for each fixed $n$, the union of the first $n$ such events is null. Thus ${\bar{Y}}_n=\theta$ almost surely for each $n$, and the centered sample mean has law ${\delta }_0=N(0,0)$ for every $n$ by [F10]. The variance argument in the preceding steps used no choice axiom.

Use [F8] with density $r=q$ for integration against $Q$ and with $r=\tilde{p}\mathrm{/}{Z}_p$ for integration against $\pi$. By [F6], the functions $w(x)=\tilde{p}(x)\mathrm{/}q(x)$ on $q>0$ (with value $0$ on $q=0$) and $v(x)=w(x)f(x)$ are measurable. The support condition gives $\pi (\{q=0\})=0$. For each $i$, $X_i$ has law $Q$, so the given finite first moment applies to its weight and integrand. By [F2], ${\mathbb{E}}_Q[W_i\mathrm{\mid }f(X_i)\mathrm{\mid }]={\int }_{\{q>0\}}\frac{\tilde{p}(x)\mathrm{\mid }f(x)\mathrm{\mid }}{q(x)}q(x)d\mu (x)={\int }_{\{q>0\}}\tilde{p}\mathrm{\mid }f\mathrm{\mid }d\mu \mathrm{.}$ The given finite moment therefore implies ${\int }_{\{q>0\}}\tilde{p}\mathrm{\mid }f\mathrm{\mid }d\mu <\mathrm{\infty }$. Since $\pi (\{q=0\})=0$, [F7] gives ${\int }_{\{q=0\}}\mathrm{\mid }f\mathrm{\mid }d\pi =0$, and thus ${\int }_{\{q=0\}}\tilde{p}\mathrm{\mid }f\mathrm{\mid }d\mu =Z_p{\int }_{\{q=0\}}\mathrm{\mid }f\mathrm{\mid }d\pi =0$. Hence ${\int }_{\mathsf{X}}\tilde{p}\mathrm{\mid }f\mathrm{\mid }d\mu <\mathrm{\infty }$ and $\theta =\int fd\pi$ is well-defined. For any real measurable $h$ whose absolute integral is finite against $rd\mu$, apply [F8] separately to $h^{+}=\max (h,0)$ and $h^{-}=\max (-h,0)$: both product integrals are finite because $h^{\pm }\le \mathrm{\mid }h\mathrm{\mid }$. Subtracting their finite identities yields $\int hd(rd\mu )=\int hrd\mu$, since $(hr{)}^{\pm }=h^{\pm }r$ for $r\ge 0$ (with the density convention $0\cdot \mathrm{\infty }=0$). The integrable case of [F2] now gives ${\mathbb{E}}_Q{V}_i={\int }_{\{q>0\}}\frac{\tilde{p}(x)f(x)}{q(x)}q(x)d\mu (x)={\int }_{\{q>0\}}\tilde{p}fd\mu ={\int }_{\mathsf{X}}\tilde{p}fd\mu =Z_p\theta ,$ where the omitted signed integral is zero because its absolute integral over $\{q=0\}$ is zero. Likewise, the nonnegative case of [F2] gives ${\mathbb{E}}_Q{W}_i={\int }_{\{q>0\}}\tilde{p}d\mu =Z_p$, since ${\int }_{\{q=0\}}\tilde{p}d\mu =Z_p\pi (\{q=0\})=0$. All these expectations agree across $i$ by the common law of the $X_i$.

Applying [F3] separately to the measurable maps $w$ and $v$ shows that each family $(W_i)$ and $(V_i)$ is independent. Each family has a common law because every $X_i$ has law $Q$ and the same map is applied to each draw. Thus both sequences are IID as in [F4], and [F5] gives $n^{-1}{\sum }_i{W}_i\to Z_p$ and $n^{-1}{\sum }_i{V}_i\to Z_p\theta$ almost surely.

On the probability-one event from step 1.2, the denominator average is eventually greater than $Z_p\mathrm{/}2>0$, so the ratio is eventually defined and ${\widehat{\theta }}_{\mathrm{S}\mathrm{N},n}=\frac{n^{-1}{\sum }_i{V}_i}{n^{-1}{\sum }_i{W}_i}⟶\frac{Z_p\theta }{Z_p}=\theta$. The numerical zero interpretation for any preceding finite prefix with zero denominator is the convention stated in this theorem; the algorithm itself returns the no-estimate status in [F1].

Use [F14] with density $r=q$ for integration against $Q$ and with $r=\tilde{p}\mathrm{/}{Z}_p$ for integration against $\pi$. By the support condition, $\pi (\{q=0\})=0$. For each $i$, $X_i$ has law $Q$, so the given finite first moment applies to $W_i\mathrm{\mid }f(X_i)\mathrm{\mid }$. The integrable case of [F2] gives ${\mathbb{E}}_Q[W_i\mathrm{\mid }f(X_i)\mathrm{\mid }]={\int }_{\{q>0\}}\frac{\tilde{p}(x)\mathrm{\mid }f(x)\mathrm{\mid }}{q(x)}q(x)d\mu (x)={\int }_{\{q>0\}}\tilde{p}\mathrm{\mid }f\mathrm{\mid }d\mu <\mathrm{\infty }\mathrm{.}$ By [F13], ${\int }_{\{q=0\}}\mathrm{\mid }f\mathrm{\mid }d\pi =0$, and hence ${\int }_{\{q=0\}}\tilde{p}\mathrm{\mid }f\mathrm{\mid }d\mu =Z_p{\int }_{\{q=0\}}\mathrm{\mid }f\mathrm{\mid }d\pi =0$. Thus ${\int }_{\mathsf{X}}\tilde{p}\mathrm{\mid }f\mathrm{\mid }d\mu <\mathrm{\infty }$. For any real measurable $h$ whose absolute integral is finite against $rd\mu$, apply [F14] separately to $h^{+}=\max (h,0)$ and $h^{-}=\max (-h,0)$: both product integrals are finite because $h^{\pm }\le \mathrm{\mid }h\mathrm{\mid }$. Subtracting their finite identities yields $\int hd(rd\mu )=\int hrd\mu$, since $(hr{)}^{\pm }=h^{\pm }r$ for $r\ge 0$ (with the density convention $0\cdot \mathrm{\infty }=0$). The integrable case of [F2] applied to $W_{i}f(X_i)$ yields ${\mathbb{E}}_Q[W_{i}f(X_i)]={\int }_{\{q>0\}}\tilde{p}fd\mu ={\int }_{\mathsf{X}}\tilde{p}fd\mu =Z_p\theta ,$ because the omitted signed integral is zero by its absolute integrability on the $\pi$-null set. The nonnegative case of [F2] also gives ${\mathbb{E}}_Q{W}_i={\int }_{\{q>0\}}\tilde{p}d\mu =Z_p$, since ${\int }_{\{q=0\}}\tilde{p}d\mu =Z_p\pi (\{q=0\})=0$. The second-moment assumptions make $Z_i$ square-integrable. The map $x\mapsto (w(x),w(x)f(x))$ is measurable by [F1] and [F12]. Applying [F7] to this map proves that the pairs $Z_i$ are independent; their laws agree because each $X_i$ has law $Q$ and the same map is applied, so they are IID by [F8]. Therefore [F3] and [A1] give $\sqrt{n}(({\bar{W}}_n,{\bar{V}}_n)-(Z_p,Z_p\theta ))\Rightarrow N_2(0,\mathrm{\Sigma })$, where $\mathrm{\Sigma }={\mathrm{Cov}}_Q(Z_1)$.

Put $U_i=W_i^2(f(X_i)-\theta {)}^2$, $C_i=W_i^2(f(X_i)-\theta )$, and $B_i=W_i^2$. Their measurability follows from [F12]. The stated second moments and $(W_{i}f(X_i)-\theta W_i{)}^2\le 2(W_{i}f(X_i){)}^2+2{\theta }^2{W}_i^2$ give $\mathbb{E}{U}_i<\mathrm{\infty }$ and $\mathbb{E}{B}_i<\mathrm{\infty }$; [F11] gives $\mathbb{E}\mathrm{\mid }{C}_i\mathrm{\mid }\le (\mathbb{E}{U}_i{)}^{1\mathrm{/}2}(\mathbb{E}{B}_i{)}^{1\mathrm{/}2}<\mathrm{\infty }$. Each transformed sequence is IID by [F7] and [F8], so [F6] applies to all three. Also $(W_i)$ is IID and integrable, with mean $Z_p$ by step 1.1; applying [F6] to this sequence gives ${\bar{W}}_n\to Z_p>0$ almost surely. Separately, [F5] gives ${\widehat{\theta }}_{\mathrm{S}\mathrm{N},n}\to \theta$ almost surely.

Define the Borel function $g(s,t)=t\mathrm{/}s$ for $s>0$ and $g(s,t)=0$ for $s\le 0$; it is Borel because the ratio is continuous on the open set $s>0$ and the other branch is constant on its Borel complement. At $\eta =(Z_p,Z_p\theta )$, its derivative is $A(h_1,h_2)=(-\theta h_1+h_2)\mathrm{/}{Z}_p$: for $h_1$ small enough that $Z_p+h_1>0$, $g(\eta +h)-g(\eta )-Ah=-\frac{h_1(h_2-\theta h_1)}{Z_p(Z_p+h_1)}=O(\mathrm{\parallel }h{\mathrm{\parallel }}^2)$. Since $Z_p>0$, this is a valid first-order expansion. Since ${\bar{W}}_n\ge 0$, $g({\bar{W}}_n,{\bar{V}}_n)$ equals the ratio when $S_n>0$; when $S_n=0$, it equals the numerical value $0$ prescribed by the Statement. Thus $g({\bar{W}}_n,{\bar{V}}_n)={\widehat{\theta }}_{\mathrm{S}\mathrm{N},n}$ for every $n$, including the zero-weight branch where [F1] returns a status. Apply [F4] to step 1.1 to obtain the scalar limit $AZ$, where $Z\sim N_2(0,\mathrm{\Sigma })$.

By [F10], $AZ$ is centered normal with variance $A\mathrm{\Sigma }{A}^T$. The centered linear combination of $Z_1$ defining this variance is $Z_p^{-1}(W_{1}f(X_1)-\theta W_1)$, whose mean is zero by [F2]. Therefore $A\mathrm{\Sigma }{A}^T=Z_p^{-2}{\mathbb{E}}_Q[W_1^2(f(X_1)-\theta {)}^2]={\tau }^2$, which proves the stated CLT.

On the probability-one event from step 2.1 the denominator is eventually positive, and expansion of the squared residual gives $n{\stackrel{}{\mathrm{Var}}}_{\mathrm{M}\mathrm{C}}=\frac{{\bar{U}}_n-2({\widehat{\theta }}_{\mathrm{S}\mathrm{N},n}-\theta ){\bar{C}}_n+({\widehat{\theta }}_{\mathrm{S}\mathrm{N},n}-\theta {)}^2{\bar{B}}_n}{{\bar{W}}_n^2}$. The numerator tends to $\mathbb{E}{U}_1$ and the denominator tends to $Z_p^2$, so the limit is $Z_p^{-2}\mathbb{E}{U}_1={\tau }^2$. Continuity of the nonnegative square-root map gives $\sqrt{n}{\stackrel{}{\mathrm{se}}}_{\mathrm{M}\mathrm{C},n}\to \tau$. This argument uses only the choice-free suppliers [F5], [F6], [F7], [F8], [F11], and [F12], not AC.