Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 216 / 1

Put $a=y_4$ and $b=y_2+y_3$. Dropping factors independent of $\theta$, the multinomial likelihood and uniform prior give the posterior densityMultiplying this by the stipulated binomial distribution for the latent variable cancels the factor $(2+\theta {)}^{y_1}$:Consequently the two full conditional distributions areStart with $0<{\theta }_0<1$, sample $Z$ from its binomial distribution, then sample a new $\theta$ from its Beta distribution, and repeat. The binomial distribution can be sampled by adding $y_1$ independent Bernoulli random variables. For the Beta distribution, take independent $A\sim \mathrm{Gamma}(a+z+1,1)$ and $B\sim \mathrm{Gamma}(b+1,1)$ and return $A/(A+B)$; integer-shape gamma distributions are sums of independent unit-rate exponential distributions. Both shapes are positive even when some observed counts vanish.

Each Gibbs sampler update preserves the augmented posterior distribution, so its $\theta$ marginal distribution is the required posterior distribution. The positive full conditional distributions on the interior allow exploration of the entire support. These iterates are generally dependent; they are not the independent exact draws constructed in the later parts.

Adaptive rejection sampling is exact rejection sampling for a differentiable log-concave probability density. Given interior evaluation points $s_j$, construct the upper envelopewhere $h$ is the unnormalized target probability density function. The concave function $\ell$ lies below all its tangent lines, so $e^u\ge h$. Interpolation between adjacent evaluation points gives a lower envelope $l\le \ell$ there, allowing a squeeze test. The normalized upper envelope $g=e^u/\int e^u$ is a piecewise exponential proposal distribution.

Draw $X\sim g$ and an independent $W$ from the uniform distribution, and accept when $W\le e^{\ell (X)-u(X)}$. A squeeze test $W\le e^{l(X)-u(X)}$ can establish acceptance without evaluating $\ell (X)$. Otherwise evaluate $\ell (X)$ and, whenever it is evaluated, add $X$ to the envelope's points. Repeat until acceptance. On each linear piece $u(x)=rx+s$, its integral is $e^s(e^{rd}-e^{rc})/r$ on $[c,d]$, with value $e^s(d-c)$ when $r=0$. These integrals select a piece; inverse transform sampling samples within it.

Here, with $a=y_4$ and $b=y_2+y_3$, the log-posterior on $(0,1)$ hasChoose evaluation points strictly inside $(0,1)$, avoiding any endpoint singularities of the logarithm. Every finite set of tangent lines gives a finite upper-envelope integral on this bounded interval; slope conditions needed for unbounded supports are unnecessary. When $N=0$ the posterior distribution is simply the uniform distribution and may be sampled directly.

For any fixed envelope, proposal times acceptance is proportional to $h(x)$. Conditional on all past evaluations and rejections, the next accepted value therefore has the same normalized posterior density. To see that adaptation does not spoil this, at every attempted draw its accepted mass is a scalar times that fixed posterior density; summing over possible rejection histories preserves it. The acceptance probability stays bounded below by its positive initial-envelope value because insertion only lowers the upper envelope. Thus acceptance occurs almost surely. With fresh independent randomness, successive accepted values are exact independent samples from the posterior distribution, even when the envelope is retained and improved between them.

An exact finite mixture model follows from the binomial theorem:Define positive mixture weightsHere $B$ is the Beta function, so the component probability distributions are $\mathrm{Beta}(a+z+1,b+1)$. All coefficients are computable from the observed integer counts.

Use inverse transform sampling with the supplied $U$ to choose $Z$: writing $C_{-1}=0$ and $C_z={\sum }_{j=0}^z{w}_j$, take $C_{Z-1}\le U<C_Z$. Then recycle its position inside that interval,Recycling a uniform random variable after discrete sampling makes $V$ uniform independently of $Z$, since $\mathrm{Pr}(Z=z,V\le v)=w_{z}v$. It is also independent of all supplied random variables with gamma distributions. Transform these by the probability integral transform:They are independent random variables with uniform distributions because $G_i$ has a unit-rate exponential distribution.

Conditional on $Z=z$, put $k=a+z+b+1$ and $r=a+z+1$. Form the $k$ values $V,W_1,\dots ,W_{k-1}$ and return their $r$th order statistic. This uses at most the supplied $N$ random variables with gamma distributions, since $k-1=a+b+z\le N$. The uniform order statistic formula givesAveraging these component probability density functions with weights $w_z$ recovers exactly the normalized posterior density. Unused inputs can be discarded. When $N=0$, $Z=0$, $k=r=1$, and the output is $U$, as required. Interval endpoints and ties have probability zero; any consistent convention there is harmless. Exactness here concerns the mathematical algorithm; finite-precision arithmetic can be stabilized with logarithmic mixture weights.