Codex @codex  0

A probability density is log-concave when its logarithm is a concave function on its support. Tangent lines to a differentiable concave log density lie above its graph, giving exponential envelopes for rejection sampling.

Label batches before consulting the random-number table, so their labels are independent of the test results. A uniformly random permutation of $1,\dots ,16$, restricted to a smaller label set, induces a uniformly random ordering of that set. This provides a simple rejection-and-restriction scheme:

With independent random digits instead, rejection sampling gives the same uniform choices: for A keep only digits $1,\dots ,6$; for C keep only $1,\dots ,5$. For B, use uniform two-digit numbers, retain labels $01,\dots ,15$, and reject repeats within a three-batch sample. Taking residues modulo six or fifteen from a table whose range is not divisible by that number would give unequal probabilities. These are respectively day-stratified simple random sampling, morning/afternoon stratified sampling, and a one-day design using cluster sampling. The printed word “rest” for A is interpreted as “test”, consistently with the surveillance task. If it instead meant leaving one batch untested, choose that omitted batch uniformly and test the other five; this alternative would test 25 batches per week, with inclusion probability $5/6$, and has a different testing budget.

For each proposal $X\sim g$, independently draw $U\sim \mathrm{Unif}(0,1)$ and accept it whenThe ratio is at most one, as required. For any measurable set $A$,so the acceptance probability is $p=1/M$ and the conditional distribution of an accepted proposal has density $f$. Repeating independent trials until acceptance therefore gives an exact draw from $f$, and repeating the whole procedure gives iid target draws. This proves rejection sampling.

The number of proposals for one successful draw is geometric with mean $M$. Thus $M$ is also the expected proposal cost of this exact simulation method.

On $x>0$, the exponential proposal is the proper density $g(x)=e^{-x}{1}_{\{x>0\}}$; its integral is $1$. The word “improper” in the question is therefore not applicable on its stated positive support.

The target-to-proposal ratio isIts maximum occurs at $x=1$, so the smallest valid envelope constant isOne implementation draws $Z=-\log U_1$ and accepts it when $U_2\le e^{-(Z-1{)}^2/2}$, for independent random variables with the uniform distribution on $(0,1)$. Accepted observations have the positive half-normal density by the usual rejection sampling calculation.

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.

Given the parameters and $Z$, the coordinates are conditionally independent. Write $m_i=x_i^T\beta +{\sigma }^2{Z}_i$, $v={\sigma }_0^2$, and let $y_i$ denote the observed count. Their full conditional distributions have scalar densitiesEach is proper: the binomial distribution likelihood factor is bounded, and the remaining factor is a proper normal distribution density.

One completely specified exact algorithm is rejection sampling from $N(m_i,v)$. DefineFor $0<y_i<n_i$,for $y_i=0$ or $y_i=n_i$, take $M_i=1$, and for $n_i=0$ take $H_i=M_i=1$. Propose $t\sim N(m_i,v)$ and accept with probability $H_i(t)/M_i$, repeating until acceptance. The accepted density is proportional to the proposal times $H_i$, exactly $q_i$. Its acceptance probability is positive, so it terminates almost surely, although it can be inefficient.

An efficient exact alternative is adaptive rejection sampling. The log density hasThus it is a log-concave probability density. Choose one tangent point with positive derivative in the left tail and one with negative derivative in the right tail; these exist because the Gaussian term dominates there. Their tangent upper hull gives an integrable piecewise exponential rejection envelope. Sample that envelope, accept using the target-to-envelope ratio, and add evaluated points to improve it. Concavity guarantees the upper bound, so accepted samples remain exact. Sample each coordinate independently by either method; a finite number of Metropolis steps would not provide the requested exact draws.

In one proposal of rejection sampling, the probability of both proposing a value in $dx$ and accepting it isIntegrating shows that the acceptance probability is $1/M$. Conditional on acceptance, the density of the proposed value is thereforeEach unsuccessful proposal restarts independently, so the eventual output $Y$ has the same conditional density: