Past exam of the Probability, statistics and options II course of the University of Oxford / 2010 / S (Simulation)

Independently draw $Y\sim q$ and $U\sim \mathrm{Uniform}(0,1)$. Accept $Y$ if $U\le p(Y)/(Mq(Y))$; otherwise discard it and repeat with fresh independent draws. Return the first accepted value. The bound makes the acceptance probability at each proposal at most one. As $\int p=1$, the total acceptance probability is $1/M>0$, so the procedure terminates almost surely. Values outside the proposal support must have target density zero for the stated envelope assumption to make sense.

For one trial and any measurable set $A$,Since the acceptance probability is $1/M$, conditioning gives target probability ${\int }_{A}p$. Repeating failed independent trials does not alter this conditional law: summing over the trial number multiplies by the geometric sum ${\sum }_{j\ge 0}(1-1/M{)}^j/M=1$. Taking $A=(-\infty ,x)$ proves

Generate independent standard normal variables $Z_1,Z_2$ and put $\boxed{Y=Z_1/Z_2}$. The event $Z_2=0$ has probability zero. The ratio calculation in M4 with equal standard deviations gives density $1/[\pi (1+y^2)]$, exactly the required $t$ distribution with one degree of freedom. The equivalent form $Z_1/|Z_2|$ has the same law by symmetry.

For $x\ne 0$, the envelope ratio isIf $|x|\le 1$, use $|\sin x|\le |x|$ to bound this by $\frac{3}{2}(1+x^2)\le 3$. If $|x|\ge 1$, use $|\sin x|\le 1$ to bound it by $\frac{3}{2}(x^{-4}+x^{-2})\le 3$. The boundary equalities in these bounds cannot both occur in the sine estimate, so $M=3$ is a valid envelope. At zero the continuous ratio is $3/2$.

Generate independent Cauchy proposals as in (i), together with independent uniform $U$. Accept a proposal $Y$ whenusing the limiting value $1/2$ at $Y=0$. Repeat until acceptance. Part (a) proves exactness; the overall acceptance rate is $1/3$ and the mean number of proposals is three. No numerical maximization of the ratio is needed for correctness.