= Solution
<Adaptive rejection sampling> is exact <rejection sampling> for a differentiable <log-concave probability density>. Given interior evaluation points $s_j$, construct the upper envelope
$$
u(x)=\min_j\{\ell(s_j)+\ell'(s_j)(x-s_j)\},\qquad \ell(x)=\log h(x),
$$
where $h$ is the unnormalized target <probability density function>. The <concave function> $\ell$ lies below all its <tangent lines>, so $e^u\geq h$. Interpolation between adjacent evaluation points gives a lower envelope $l\leq\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\leq e^{\ell(X)-u(X)}$. A squeeze test $W\leq 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)=r x+s$, its <integral> is $e^s(e^{r d}-e^{r c})/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)$ has
$$
\ell(\theta)=y_1\log(2+\theta)+a\log\theta+b\log(1-\theta),\qquad
\boxed{\ell''(\theta)=-\frac{y_1}{(2+\theta)^2}-\frac{a}{\theta^2}-\frac{b}{(1-\theta)^2}\leq0.}
$$
Choose 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 \b[exact <independent> samples from the <posterior distribution>], even when the envelope is retained and improved between them.
Back to article page
