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

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.