Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 208 / 5

Let $Y_i$ be iid with density $f$, set $H_i=h(Y_i)$, and put $I=E_{f}h(Y)$ and ${\tau }^2={\mathrm{Var}}_f(h(Y))$. The finite-second-moment assumption gives, for ${\tau }^2>0$,The sample variance $s_N^2=(N-1{)}^{-1}{\sum }_i(H_i-{\hat{I}}_N{)}^2$ consistently estimates ${\tau }^2$. The central limit theorem and Slutsky theorem therefore give the asymptotic confidence intervalIts confidence probability is approximately $1-\alpha$, conventionally written $100(1-\alpha )\%$; the printed $(1-\alpha )\%$ omits the factor $100$. For ${\tau }^2=0$, $h(Y)=I$ almost surely and the estimator has zero error. This interval concerns iid Monte Carlo estimators; correlated simulation output requires a long-run variance of a stationary process estimate instead of the iid sample variance.

The support condition for importance sampling is missing from the printed assertion. Assume $M>1$, $E_f|h|<\infty$, and $Mg(z)>f(z)$ for $f$-almost every $z$. For a proposal $Z\sim g$, rejection has conditional probability $1-f(Z)/(Mg(Z))$. Its unconditional probability is $(M-1)/M$, so the conditional density of a rejected draw isThus the rejected-draw weight is precisely $f(z)/r(z)$, andConditionally on any positive rejection count $n$ among $N$ independent proposals, the rejected locations have this iid conditional density. Henceis an unbiased estimator conditionally on $n$, and therefore also conditionally on the event $0<n<N$. This is importance sampling from the rejected-proposal distribution.

The nonstrict assumption $f\le Mg$ alone does not suffice: the rejected distribution may completely miss part of the target support. For example, let $g$ be uniform on $[0,1]$, $f(z)=21_{[0,1/2]}(z)$, $M=2$, and $h=1$. All rejected proposals lie in $(1/2,1]$, where $f=0$, so the displayed estimator is always $0$, whereas $E_{f}h=1$. This remains a counterexample after conditioning on $0<n<N$. A strict envelope, such as choosing $M$ larger than the essential supremum of $f/g$, repairs the missing support condition. Near-equality can still give high-variance weights, even when it remains an unbiased estimator.

On $x>0$, the exponential proposal is the proper density $g(x)=e^{-x}{1}_{\{x>0\}}$; its integral is $1$. The word “improper” in the question is therefore not applicable on its stated positive support.

The target-to-proposal ratio isIts maximum occurs at $x=1$, so the smallest valid envelope constant isOne implementation draws $Z=-\log U_1$ and accepts it when $U_2\le e^{-(Z-1{)}^2/2}$, for independent random variables with the uniform distribution on $(0,1)$. Accepted observations have the positive half-normal density by the usual rejection sampling calculation.

The printed identity needs an expectation on its right-hand side. For fixed $r\ge 1$, condition on $X_2,\dots ,X_r$ and use independence of $X_1$:The expression inside this expectation is generally random and cannot equal the unconditional probability by itself.

For each independent Monte Carlo method replicate, draw $R_j$ from its given distribution. If $R_j=r\ge 1$, draw $r-1$ independent $F$-variables, form $W_j={\sum }_{i=2}^r{X}_{j,i}$ and set $H_j=F(x-W_j)$. For $r=1$ the empty sum is $0$. If $R$ may equal zero, use $H_j=1_{\{x\ge 0\}}$ when $R_j=0$, since $S_0=0$. The law of total expectation givesSince $0\le H_j\le 1$, the estimator has statistical consistency by the strong law of large numbers. It is the conditional Monte Carlo estimator obtained by Rao-Blackwellization of the direct indicator $1_{\{S_R\le x\}}$, and the law of total variance gives $\mathrm{Var}(H_j)\le l(1-l)$.

This version assumes that the cumulative distribution function $F$ can be evaluated. An easy sampler alone does not automatically supply an easy cumulative distribution function evaluation. If only sampling is available, use the direct indicator estimator, or replace each conditional cumulative distribution function by the average of several independent indicators $1_{\{X_{j,1,k}\le x-W_j\}}$; the nested version remains an unbiased estimator. With $L$ such inner draws its variance per outer replicate is $\mathrm{Var}(H_j)+L^{-1}E[H_j(1-H_j)]$.