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

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.