Past exam of the simulation and statistical programming course of the University of Oxford / 2023 / 1

Generate independent and identically distributed random variables $X_1,\dots ,X_n$ with probability density function $p$, evaluate $\varphi (X_i)$ for each draw, and return the Monte Carlo estimatorLinearity of expectation makes this an unbiased estimator: $\mathbb{E}{\hat{\theta }}_n^{\mathrm{MC}}=\theta$. Independence and the specified variance give $\mathrm{Var}({\hat{\theta }}_n^{\mathrm{MC}})=1/n$. Its Monte Carlo standard error is therefore $n^{-1/2}$, and the strong law of large numbers gives convergence to $\theta$ almost surely.

Apply Chebyshev's inequality to the Monte Carlo estimator:Thus $10^4/n\le 0.01$ suffices, givingThis is a finite-sample probability guarantee for every target satisfying the given variance assumption. It is a sufficient sample count supplied by the inequality, rather than a claim that every such target actually needs a million draws.

The central limit theorem gives $\sqrt{n}({\hat{\theta }}_n^{\mathrm{MC}}-\theta )\Rightarrow N(0,1)$, so, with $\Phi$ the cumulative distribution function of the standard normal distribution,The error has two tails. Using the supplied $2.58$ quantile, whose two-sided coverage is approximately $0.9902$, givesThe supplied $2.33$ quantile would be appropriate for a one-sided $99\%$ calculation; it would give only approximately $98.02\%$ two-sided coverage. Using the exact $0.995$ quantile instead of $2.58$ would give $66,349$ draws; we consistently use the paper's rounded value $N=66,564$ below.

For routine Monte Carlo integration, the central limit theorem calculation is preferable as a practical budget: it uses about one fifteenth as many draws as the Chebyshev's inequality bound. However, its coverage is approximate. Finite variance alone supplies no universal rate of convergence to the normal distribution; an integrand with large skewness or a heavy-tailed distribution can make the approximation poor even at a large sample count. If an unconditional finite-sample $99\%$ guarantee is required under only the stated assumptions, use the Chebyshev's inequality budget.

Integrating the envelope $p\le Mq$ shows $M\ge 1$. One trial of rejection sampling draws $Y\sim q$ and an independent $U$ from the uniform distribution on $(0,1)$, and accepts $Y$ if $U\le p(Y)/(Mq(Y))$. Repeat with fresh independent random variables after each rejection. Ratios need only be evaluated where $q>0$; the envelope makes the target zero wherever $q=0$.

For any measurable set $B$, integration of the conditional probability of acceptance givesTaking the whole domain gives acceptance probability $1/M$, and dividing gives $\mathbb{P}(Y\in B\mid \mathrm{accept})={\int }_{B}p(y)dy$. Fresh trials therefore supply independent and identically distributed random variables $X_1,\dots ,X_m$ with target probability density function $p$. The corresponding Monte Carlo estimator isThe proposal count $T$ up to and including one acceptance has the geometric distributionFor example, the tail-sum formula gives $\mathbb{E}T={\sum }_{t\ge 0}(1-1/M{)}^t=M$. Thus the expected cost is $M$ proposal draws per accepted target draw.

Stop rejection sampling when exactly $N=66,564$ target draws have been accepted. The total proposal count $T_N$ is a sum of $N$ independent waiting times with geometric distribution, equivalently a negative binomial distribution counting trials. ConsequentlyThe accepted-sample Monte Carlo estimator then has the approximate $99\%$ precision from (a)(iii). The displayed proposal cost is an expected value, which need not be an integer. Spending this many proposals in advance does not ensure that $N$ target draws will have been accepted.

With a fixed budget of $n$ independent proposal trials, the accepted count $K_n$ has binomial distribution with success probability $1/M$. HenceFor $M>1$, the central limit theorem gives the one-sided approximationUse $z=2.33$, since now only the lower tail of the accepted count matters. Requiring $n-MN\ge z\sqrt{n(M-1)}$ and solving the resulting quadratic equation in $t=\sqrt{n}$ gives the one-sided normal approximation for a rejection proposal budgetEquivalently, before rounding, this is $MN+z^2(M-1)/2+(z/2)\sqrt{(M-1)[z^2(M-1)+4MN]}$. For the value in (a)(iii),When $M=1$, every proposal is accepted and $\boxed{n_0=N=66,564}$ exactly. Otherwise the positive safety margin above $MN$ allows for random fluctuations in the number accepted. The average cost in (b)(ii) describes stopping at the $N$th acceptance; this answer chooses a deterministic budget that reaches that acceptance with approximately $99\%$ probability.

The approximation requires a sufficiently accurate normal distribution approximation to the binomial distribution. An exact $99\%$ budget can instead be found from its tail probabilities. Also, a $99\%$ chance of enough accepted draws and approximate $99\%$ precision conditional on obtaining them are separate claims: their intersection is not automatically a $99\%$ event.

Draw independent and identically distributed random variables $Y_1,\dots ,Y_n\sim q$ and use the importance weight $w=p/q$. The importance sampling estimator isThe envelope supplies the support condition for importance sampling. Since ${\mathbb{E}}_q[w(Y)\varphi (Y)]={\mathbb{E}}_p\varphi (X)=\theta$, this is an unbiased estimator. Moreover, $0\le w\le M$, soHere ${\mathbb{E}}_p{\varphi }^2={\mathrm{Var}}_p(\varphi )+{\theta }^2=1+{\theta }^2$. Subtracting the squared expected value and dividing by $n$ proves the bounded-weight importance-sampling moment bound in the requested form:

The definition of $a$ and (c)(i) give $a\le M$. Nonnegativity of the variance strengthens the lower bound toIn fact the variance of one weighted observation is exactlyIt is finite by the envelope. For $v_{\mathrm{IS}}>0$, the central limit theorem gives approximate two-sided coverage $2\Phi (0.01\sqrt{n/v_{\mathrm{IS}}})-1$, so the paper's rounded quantile yieldsIf $v_{\mathrm{IS}}=0$, the weighted observation equals $\theta$ almost surely, and one draw is sufficient. These are theoretical budgets: $a$ and $\theta$ may themselves be unknown and need preliminary estimation in an implementation.

Compare with the average rejection sampling cost $66,564M$. Ignoring integer rounding, importance sampling uses fewer proposal draws at the same approximate precision precisely whenFor literal integer budgets, the comparison is $\lceil 66,564v_{\mathrm{IS}}\rceil <66,564M$. The simpler strict inequality is the intended leading-order condition. The bound $a\le M$ alone does not ensure an improvement when $\theta \ne 0$; this is a proposal-budget variance comparison of importance and rejection sampling.