Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 47 / 3

A linear congruential generator starts with an integer seed $S_0\in \{0,\dots ,M-1\}$ and iteratesThe outputs lie in $[0,1)$ and are used as pseudorandom numbers approximating a uniform distribution. They are deterministic once the seed is fixed. The largest possible period is $M$, since there are only $M$ states; good period alone does not establish independence or good multivariate uniformity.

The full-period criterion for a mixed congruential generator says that period $M$ for every seed occurs exactly whenFor $M=12^k=2^{2k}{3}^k$, these conditions reduce toThe multiplier must satisfy both $a\equiv 1(\mathrm{mod}3)$ and $a\equiv 1(\mathrm{mod}4)$. A positive shift alone is insufficient: for example, a shift divisible by three cannot give period $M$ when the multiplier is one modulo three. If the required coprime shift has already been chosen, the condition on the multiplier alone is $a=1+12r$ for an integer $r$.

Use the ratio-of-uniforms method onWriting $x=v/u$ gives $u\le e^{-x^2/(4{\sigma }^2)}$ and $v=ux$. Consequentlybecause the derivative vanishes at $x=\sigma \sqrt{2}$. Thus the normal ratio-of-uniforms envelope is the rectangle $0<u<1$, $|v|<\sigma \sqrt{2/e}$.

Generate independent $U_1,U_2$ with uniform distribution on $(0,1)$, set $u=U_1$ and $v=(2U_2-1)\sigma \sqrt{2/e}$, and accept precisely whenReject and repeat otherwise. On acceptance return $X=v/u$. One can compare logarithms instead of exponentials to avoid underflow.

For a proof, the change of variables $(u,x)\mapsto (u,v=ux)$ has Jacobian determinant $u$. A uniform point in $\mathcal{R}$ therefore gives an $x$-density proportional toNormalizing yields the required normal distribution with mean zero and variance ${\sigma }^2$. The region area is $\frac{1}{2}\int h(x)dx=\sigma \sqrt{\pi /2}$; dividing it by the rectangle area $2\sigma \sqrt{2/e}$ gives acceptance probability $\sqrt{\pi e}/4$.

For $\alpha ,\beta >0$, integrating the Weibull distribution probability density function givesThe inverse transform sampling method takes $U$ uniform on $(0,1)$ and solves $G(X)=U$. HenceSince $1-U$ is also uniform, $\{-\beta \log U{\}}^{1/\alpha }$ is an equivalent implementation. For any $x\ge 0$, the resulting event $X\le x$ has probability $G(x)$, verifying its distribution.

Assume $0\le p\le 1$. Draw an independent component indicator with a Bernoulli distribution of success probability $p$. On success, generate the normal distribution from part (i) and return its absolute value; this has the half-normal distribution probability density function $2f(x)$ on $x\ge 0$. On failure, generate the Weibull distribution from part (ii). Use fresh independent uniforms for the chosen component.

The law of total probability gives the output probability density functionas required. The factor two belongs inside the half-normal component; the probability of choosing that component is $p$, not $2p$.