Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 36 / 4

Let $w(x)=f(x)/g(x)$ where $g(x)>0$, and set it to zero on the g-null set where $g=0$. The domination assumption makes $f=0$ there and gives $0\le w\le M$. Integrating it also gives $M\ge 1$. For iid proposals $X_i\sim g$, the importance sampling estimator isCauchy-Schwarz inequality under $f$ gives $|\theta |\le (\int {\varphi }^{2}f{)}^{1/2}<\infty$. Direct integration proves unbiasedness, ${\mathbb{E}}_g[\varphi (X)w(X)]=\theta$. MoreoverThusThe iid central limit theorem applies to these finite-variance weighted observations:If the variance is zero, this denotes the point mass at zero. This is the bounded-weight importance-sampling moment bound.

For each proposal $X\sim g$, independently draw $U\sim \mathrm{Unif}(0,1)$ and accept it whenThe ratio is at most one, as required. For any measurable set $A$,so the acceptance probability is $p=1/M$ and the conditional distribution of an accepted proposal has density $f$. Repeating independent trials until acceptance therefore gives an exact draw from $f$, and repeating the whole procedure gives iid target draws. This proves rejection sampling.

The number of proposals for one successful draw is geometric with mean $M$. Thus $M$ is also the expected proposal cost of this exact simulation method.

Apply independent uniforms to the $n$ proposals, and let $I_i$ indicate acceptance. Each $I_i$ is Bernoulli with success probability $p=1/M$, and the indicators are independent because the pairs $(X_i,U_i)$ are independent. HenceFor a fixed acceptance pattern, the values at accepted positions are independent with density $f$, by the single-trial conditional density calculation. The same product law holds for every pattern of a given size. Consequently, conditional on $N=m$, the ordered accepted observations have joint density ${\prod }_{j=1}^{m}f(y_j)$. This is the binomial count and iid values in fixed-budget rejection sampling; the count provides no information about those target values.

There is a finite-sample empty-output event, with probability $(1-1/M{)}^n$. Any estimator dividing by $N$ must be defined separately on $N=0$.

Write $p=1/M$ and $v_f=\int {\varphi }^{2}f-{\theta }^2$. The Bernoulli central limit theorem givesIf $M=1$, all proposals are accepted and this limit is degenerate.

Conditional on $N=m$, the accepted sample is iid from $f$. Since $N/n\to p>0$, its size tends to infinity, and the ordinary target-sample CLT therefore givesAssign any fixed value to the estimator on $N=0$; the probability of that event tends to zero, so it does not change this limit. This is the random-count central limit theorem for accepted rejection samples.

For comparison at the same budget of $n$ proposals, Slutsky's theorem rescales this asThe distinction between accepted-sample size and proposal count is essential for the final efficiency comparison.

At a common proposal budget, the two asymptotic variances areThus prefer the estimator with the smaller proposal-budget variance; the stated assumptions do not give a universal winner. Importance sampling uses every proposal and avoids an empty accepted sample, but those facts alone do not establish variance dominance. The bound from part (a) only says $v_{\mathrm{IS}}\le M{v}_f+(M-1){\theta }^2$. If $\theta =0$, it does imply that importance sampling is at least as efficient asymptotically.

For explicit nonconstant counterexamples in both directions, take $g(x)=1$ and $f(x)=2x$ on $0<x<1$, and zero outside, with the sharp envelope $M=2$. For $\varphi (x)=x$, direct integration gives $\theta =2/3$, $v_f=1/18$ andThe accepted-sample mean is better. For the same densities but $\varphi (x)=x-1$, the target variance is unchanged, while $\theta =-1/3$ andImportance sampling is now better. This is the variance reversal under additive shifts of an importance-sampling integrand.

There is a useful distinction about the Rao-Blackwell theorem. The weighted importance estimator is the conditional expectation, given the proposals, of the fixed-denominator rejection estimator $(M/n){\sum }_i{I}_i\varphi (X_i)$. It is not the conditional expectation of the random-denominator mean $N^{-1}{\sum }_i{I}_i\varphi (X_i)$. Rao-Blackwell variance reduction for the former therefore does not prove a comparison with the latter. This is the Rao-Blackwell identity for a fixed-denominator rejection estimator. The appropriate answer is the proposal-budget variance comparison of importance and rejection sampling, with the empty-output convention specified.