Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 40 / 3

Treat the supplied uniform variates as independent $U(0,1)$ draws, as required for Monte Carlo simulation. Use $n$ of them and returnEach indicator has a Bernoulli distribution of parameter $p$, and the indicators are independent. For any subset of $r$ successes the probability is $p^r(1-p{)}^{n-r}$; there are $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ such subsets. Thus $\mathbb{P}(X=r)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)p^r(1-p{)}^{n-r}$, the binomial distribution. The construction includes the cases $p=0,1$ and $n=0$.

For rate $\lambda >0$, returnFor $x\ge 0$, $\mathbb{P}(X>x)=\mathbb{P}(U_1<e^{-\lambda x})=e^{-\lambda x}$, so $X$ has the exponential distribution of rate $\lambda$. This is inverse transform sampling; using $-\log (1-U_1)/\lambda$ is equivalent. Uniform draws at exact endpoints can be excluded, since those events have probability zero under the ideal continuous law.

Use uniform-envelope rejection sampling for a beta distribution. Put $r(x)=x^{a-1}(1-x{)}^{b-1}$ for $0<x<1$ and choose $M=\sup r$. For $a,b>1$, differentiation of $\log r$ gives the mode $(a-1)/(a+b-2)$, soIf $a=1$ or $b=1$, take $M=1$; this also covers $a=b=1$. Draw $X=U_{2j-1}$ and accept it ifOtherwise continue with the next independent pair. The probability of acceptance is ${\int }_0^{1}r(x)dx/M=B(a,b)/M>0$, so the procedure terminates almost surely. Conditional on acceptance, the probability density function is proportional to $r(x)$, hence is exactly the beta distribution of parameters $a,b$. The restriction $a,b\ge 1$ guarantees the bounded uniform envelope.

For $\sigma >0$, use the unnormalized normal shape $h(x)=e^{-x^2/(2{\sigma }^2)}$. The ratio-of-uniforms method samples uniformly fromIts boundary is $|v|\le 2\sigma u\sqrt{-\log u}$. The largest possible $|v|$ occurs at $u=e^{-1/2}$ and equals $b=\sigma \sqrt{2/e}$, giving the normal ratio-of-uniforms envelope $0<u<1$, $-b<v<b$.

Use independent uniform pairs to propose $u=U_{2j-1}$ and $v=b(2U_{2j}-1)$. Accept precisely whenTo verify its distribution, change coordinates from $(u,v)$ to $(u,x)$, with $v=ux$ and Jacobian determinant $u$. The accepted point is uniform on $\mathcal{A}$, and the marginal probability density function of $x$ is proportional toThus the result is $N(0,{\sigma }^2)$. The region has positive finite area $\sigma \sqrt{\pi /2}$, and the acceptance probability is $\sqrt{\pi e}/4$. The case $\sigma =0$ requires simply returning zero.