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

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.