Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 208 / 4

Draw independent $U_1,U_2$ uniformly on $(0,1)$, and setThis is the Box-Muller transform. The endpoint $U_1=0$ has probability zero; an implementation should avoid evaluating its logarithm.

For $r\ge 0$, $P(R\le r)=1-e^{-r^2/2}$, so $R$ has density $r{e}^{-r^2/2}$. It is independent of the angle, which has a uniform distribution on $[0,2\pi )$, and their joint density is $(2\pi {)}^{-1}r{e}^{-r^2/2}$. Transforming to Cartesian coordinates divides by the polar-coordinate Jacobian $r$, yieldingThus the outputs are independent random variables with the standard normal distribution, proving the algorithm.

Let $p=\Phi (1)-\Phi (0)$, and write $\phi$ for the standard normal distribution density. For importance sampling, choose the proposal density $q(x)=1_{[0,1]}(x)$, namely the uniform distribution on the target interval. Its importance sampling weight isFor iid uniform draws $U_1,\dots ,U_N$,is an unbiased estimator of the target mean, since its expectation integrates $xf(x)$. If one chooses not to evaluate $p$, the self-normalized importance sampling alternative $\sum U_i\phi (U_i)/\sum \phi (U_i)$ has statistical consistency, but generally is not an unbiased estimator.

Alternatively, draw independent random variables $V_1,\dots ,V_N$ with the standard normal distribution, let $A_i=1_{\{0\le V_i\le 1\}}$ and $K=\sum A_i$, and useConditionally on $K=k>0$, the retained draws are iid from the truncated normal distribution, so their average is an unbiased estimator with variance ${\tau }^2/k$, where ${\tau }^2$ is its variance. If $K=0$ the ratio is undefined; one can continue drawing until a prescribed number of retained observations is obtained.

Here importance sampling uses every draw inside the interval, whereas only $p\approx 0.3413$ of the normal proposals are retained. The advantage can also be quantified. Integration using ${\phi }^{\prime }(x)=-x\phi (x)$ givesFor uniform importance sampling,For the retained-draw ratio with a fixed total proposal budget, its asymptotic variance coefficient is ${\tau }^2/p\approx 0.233347$. Thus this importance choice has substantially smaller error for the same proposal count; it also avoids wasting about two thirds of the standard normal distribution draws. This comparison is specific to this well-matched importance sampling proposal; arbitrary proposal choices do not share this guarantee.

Use the spectral theorem for real symmetric matrices to write $\Sigma =Q\Lambda Q^T$, with $Q$ orthogonal and $\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)$, ${\lambda }_i\ge 0$. Set $L=Q{\Lambda }^{1/2}$ and generateThen $L{L}^T=\Sigma$. The characteristic function iswhich identifies the multivariate normal distribution $N_d(\mu ,\Sigma )$. Equivalently, every linear combination is normal, with the required mean and variance. A Cholesky decomposition can be used for a positive-definite matrix. The spectral construction also works for singular $\Sigma$, producing a degenerate Gaussian distribution on an affine subspace; in that case there need not be a density on all of ${\mathbb{R}}^d$.

Use $v={\sigma }^2$ as the variance parameter, with prior density relative to $d\mu dv$. Let $\bar{x}=n^{-1}\sum x_i$ and $S=\sum (x_i-\bar{x}{)}^2$. Multiplying the prior by the likelihood function gives the unnormalized Bayesian posteriorThe printed request for an “improper posterior” should not be read as a claim that this posterior is always improper. Although the prior is improper, integrating over $\mu$ gives a marginal kernel $v^{-(n+1)/2}{e}^{-S/(2v)}$, which is integrable exactly when $n>1$ and $S>0$. Under these usual nondegenerate-data conditions it is a proper posterior. If those conditions fail, the displayed kernel is improper and there is no posterior probability distribution for a sampler to target.

Completing the square and using the inverse-gamma distribution give the full conditionalsThe inverse-gamma distribution convention is density proportional to $v^{-\alpha -1}{e}^{-\beta /v}$. Equivalently the precision satisfiesusing shape and rate, as in the question.

A Gibbs sampler starts from $v^{(0)}>0$ and alternatesThis is the normal mean-variance posterior with a log-uniform variance prior. For a marginal check, $v\mid x\sim \mathrm{IG}((n-1)/2,S/2)$: integrating out $\mu$ reduces the shape by $1/2$. This marginal shape is different from the full-conditional shape $n/2$.