Rejection sampling

Suppose $f$ is a target probability density and $h$ is a proposal density with $f(x)\le Mh(x)$. Draw $X\sim h$ and an independent $U\sim \mathrm{Uniform}[0,1]$, and accept $X$ whenThe accepted value has density $f$, the acceptance probability is $1/M$, and the expected number of proposals is $M$.

Stopping after a fixed number of rejection sampling proposals preserves the target law of accepted labels, conditional on the number accepted. Stopping instead after a fixed amount of elapsed computing time can change the finite-sample law if processing costs depend on the proposed state. The deadline may censor precisely the expensive states.

For an exact counterexample, let both target and proposal be uniform on two states, so every proposal is accepted. Let processing cost be one time unit for the first state and two for the second. Stop between one and two units and retain only finished proposals. Conditional on obtaining an output, the first state is the only possible value, despite its target probability being one half. This proves that a runtime cutoff need not be an unbiased stopping rule for the realized finite output. It does not imply asymptotic bias of the indefinitely growing completed sequence; it identifies a finite-horizon censoring effect.

Consider independent rejection sampling trials with proposal density $q$, accepted-value density $f$, acceptance probability $a\in (0,1)$ and rejection probability $r=1-a$. Splitting the proposal law by its accept/reject outcome gives $q=af+r{g}_R$, where $g_R$ is the rejected-proposal distribution.

If an algorithm permits $n$ trials, returns the first accepted value when one occurs, and otherwise returns the final rejected proposal, its output density is the displayed mixture. The event of $n$ failures has probability $r^n$ and gives the conditional law $g_R$; every successful stopping trial gives law $f$. Hence the forced return introduces bias unless $g_R=f$, and its contribution decays geometrically with the cap. Conditional on success before any specified trial, the output still has law $f$, since accepted value and successful-trial index are independent.

For a Poisson distribution target of mean $\lambda >0$ and a geometric distribution proposal with probability mass function $q_k=(1-t)t^k$ on the nonnegative integers, the tight rejection sampling envelope isSuccessive target-to-proposal ratios have ratio $\lambda /[t(k+1)]$, proving this maximizing index. The function $\log M(t)$ is the maximum of the convex functions $-\lambda -\log (1-t)+k\log (\lambda /t)-\log (k!)$. Within a branch its derivative is $(1-t{)}^{-1}-m/t$.

Writing $K=\lceil \lambda \rceil$, the optimum is $t_{\ast }=\min \{\lambda /K,K/(K+1)\}$, and the success parameter is ${\rho }_{\ast }=1-t_{\ast }$. For $K-1<\lambda \le K^2/(K+1)$, $t_{\ast }=\lambda /K$ is a branch boundary; the left and right derivatives are nonpositive and nonnegative respectively. For $K^2/(K+1)<\lambda \le K$, the active branch has a zero derivative at $t_{\ast }=K/(K+1)$, including a tie at the upper endpoint. Convexity proves global optimality. The minimum expected proposal count is $M(t_{\ast })$; no claim about machine-specific instruction costs is implied.

Draw proposals with probability density function or probability mass function $q$, independently draw $U$ from the uniform distribution on $(0,1)$, and repeat until $U\le h(Y)$ for a nonnegative threshold $h$. The actual acceptance probability given $Y=y$ is $a(y)=\min (1,h(y))$. If $A={\mathbb{E}}_q[a(Y)]>0$, the returned probability distribution has density or mass $q(y)a(y)/A$. Indeed the joint law of a proposal and acceptance has density or mass $q(y)a(y)$, and conditioning on acceptance divides by $A$. Summing over failed trials gives the same law and expected trial count $1/A$. Thresholds exceeding one cannot be used as unbounded reweighting factors.

A lower envelope $h$ can save evaluations of an expensive unnormalized target $\tilde{p}$ in rejection sampling. Draw $Y$ with probability density function $\tilde{q}/Z_q$ and an independent uniform distribution value $U$. Accept immediately if $U\le h(Y)/(M\tilde{q}(Y))$. Otherwise draw a fresh independent uniform distribution value $V$ and accept ifFor a fixed proposal, writing $B=M\tilde{q}(Y)$, $H=h(Y)$ and $P=\tilde{p}(Y)$ gives total acceptance probability $H/B+(1-H/B)(P-H)/(B-H)=P/B$. If $H=B$, the first stage accepts with probability one and the residual test is skipped. Thus the accepted probability density function is $\tilde{p}/Z_p$, and the overall acceptance probability is $Z_p/(M{Z}_q)$. The probability of avoiding a target evaluation on one proposal is $\int h/(M{Z}_q)$.

If $f\ge 0$, $C=\int f\in (0,\infty )$ and $f(x)\le Mg(x)$ for a proposal probability density function $g$, accept a proposal $Y$ when an independent uniform distribution value is at most $f(Y)/(Mg(Y))$. Integrating the joint acceptance probability density function gives $p_{\mathrm{acc}}=C/M$ and conditional accepted probability density function $f/C$. For $n$ independent proposals the accepted count has binomial distribution with parameters $n,C/M$.

For target density proportional to $x^{\alpha -1}{e}^{-\beta x}$ on $x>a>0$, use the Pareto distribution proposal $g(x)=b{a}^b{x}^{-b-1}$ with $b>0$. Its density ratio is proportional to $x^{\alpha +b}{e}^{-\beta x}$, maximized at $(\alpha +b)/\beta$ if that point exceeds $a$. The tight envelope yields the highest acceptance probability for this fixed proposal. An inverse draw is $a{U}^{-1/b}$ with $U$ uniformly distributed on $(0,1)$.

For $a,b>1$, the maximum of $r$ on $[0,1]$ occurs at $(a-1)/(a+b-2)$. If one parameter is one, the maximum is attained at the corresponding endpoint; if both are one, $r$ is constant. Let $M=\sup r$. Accept an independent uniform distribution proposal $X$ when another uniform draw is at most $r(X)/M$. The accepted probability density function is the beta distribution, and acceptance probability is $B(a,b)/M$.

With proper prior $\pi (\theta )$ independent of the neutral Kingman's coalescent times, propose $(\theta ,T)$ from their joint prior and accept with probability $e^{-\theta L/2}(\theta L/2{)}^k/k!$. The accepted density is proportional to the prior times the observed-count likelihood, hence is the posterior given $S=k$. The acceptance rate is the prior predictive probability $P(S=k)$. For $k>0$, divide the acceptance function by its maximum $M_k=e^{-k}{k}^k/k!$, achieved at $\theta L/2=k$, to improve the rate to $P(S=k)/M_k$ without altering the accepted distribution. For $k=0$, $M_0=1$.

For a proper prior distribution $\pi (\theta )$ independent of coalescent times $T$, let $q(T)={\prod }_{j=2}^n{\lambda }_j{e}^{-{\lambda }_j{T}_j}$ with ${\lambda }_j=\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ and $L=\sum j{T}_j$. Observing $S=k$ under an infinite sites mutation model gives posterior density $\pi (\theta )q(T)e^{-\theta L/2}(\theta L/2{)}^k/(k!m_k)$, where $m_k$ is the prior predictive probability of $S=k$. Multiplication by the conditional Poisson mass and normalization is an application of Bayes' theorem.

// Target: statistical-inference.bigb

Accepting a fresh uniform deck permutation with a probability depending only on whether its endpoint ranks match preserves uniform individual rank marginals by symmetry. It changes their joint law. For four cards of each of thirteen ranks and rejection probability $p$ on a mismatch, the accepted matching probability is $1/(17-16p)$. The two accepted ranks are independent precisely at $p=1/4$; equality of marginals alone does not imply independence.

Write $a=\nu /2$. Against an exponential distribution proposal of mean $\nu$, the chi-squared distribution density has envelope constant $M=a^a{e}^{1-a}/\Gamma (a)$. The density ratio divided by $M$ is $\exp ((a-1)(\log (y/\nu )-y/\nu +1))$. Thus generate $Y=-\nu \log U$ and accept when $\log V\le (a-1)(\log (Y/\nu )-Y/\nu +1)$ for independent uniform distributions. The inequality $\log t\le t-1$ validates the acceptance probability. The accepted probability density function is the target because rejection sampling weights the proposal by its target-to-envelope ratio.

For a nonnegative integrable function $h$ with integral $Z$, its ratio-of-uniforms region has area $Z/2$. A uniform point in the region transforms under $v=ux$ with Jacobian determinant $u$; integrating $2u/Z$ over $0<u\le \sqrt{h(x)}$ gives density $h(x)/Z$. A rectangle containing the region gives a practical rejection sampling algorithm using only uniform random variables, with acceptance $Z/(2\mathrm{area}(B))$.

For the unnormalized Laplace distribution probability density function $h(x)=e^{-|x-1|/2}$, the ratio-of-uniforms method uses $0<u\le \sqrt{h(v/u)}$. The maximum of $h$ is one. On $x\le 0$, the maximum of $x^{2}h(x)$ occurs at $x=-4$ and equals $16e^{-5/2}$. On $x\ge 0$, it occurs at $x=4$ and equals $16e^{-3/2}$. Thus the displayed rectangle contains the region. Its area is $4(e^{-3/4}+e^{-5/4})$, while the target region has area $\frac{1}{2}\int h=2$. Uniform proposals in the rectangle, accepted when $u^2\le h(v/u)$, therefore return the correct Laplace distribution with acceptance probability $[2(e^{-3/4}+e^{-5/4}){]}^{-1}$.

For the unnormalized normal density $h(x)=e^{-x^2/(2{\sigma }^2)}$, the smallest axis-aligned envelope is $0<u<1$ and $|v|\le \sigma \sqrt{2/e}$. The boundary reaches that width at $u=e^{-1/2}$. Region area is $\sigma \sqrt{\pi /2}$, so the acceptance rate is $\sqrt{\pi e}/4$, independently of $\sigma$. Multiplying $h$ by a positive constant rescales both coordinates and their areas consistently.

A finite bounding rectangle exists when $\sqrt{h(x)}$ and $x\sqrt{h(x)}$ are bounded. This is not automatic for every probability density function: tails proportional to $(1+|x|{)}^{-3/2}$ give an unbounded second coordinate. In principle any finite-area measurable region has an open envelope of finite area, decomposable up to null boundaries into disjoint dyadic rectangles. Select a rectangle with probability proportional to its area, then sample its two coordinates uniformly and reject outside the target region. The accepted point is uniform on the region, with acceptance equal to the ratio of their areas. Constructing an effective envelope remains a density-specific computational step.

For the half-normal distribution, the density ratio to $\mathrm{Exp}(\lambda )$ is maximized at $y=\lambda$. Completing the square gives the envelope constant above and acceptance probability $e^{-(y-\lambda {)}^2/2}$. Its logarithmic derivative is $\lambda -1/\lambda$, so the optimal rate is $\lambda =1$. Give an accepted nonnegative value an independent fair sign to obtain the standard normal distribution. The expected number of proposals is $M$, while the probability of rejecting one proposal is $1-1/M$; these are different quantities.

Reject pairs of independent uniform coordinates from the square until their squared radius $S$ lies in $(0,1)$. Multiply each coordinate by $\sqrt{-2\log S/S}$ to obtain two independent variables with the standard normal distribution. Squaring either gives a chi-squared variable with one degree of freedom.

For n independent proposals and an envelope constant $M$, each rejection decision succeeds with probability $1/M$. The accepted count is Bin(n,1/M). Conditional on any acceptance pattern, the accepted values have independent target density f; summing over patterns preserves that product law conditional on the count. The empty-output probability is $(1-1/M{)}^n$.

For rejection sampling with acceptance probability $1/M$, $M>1$, the accepted count in $n$ trials has binomial distribution, mean $n/M$ and variance $n(M-1)/M^2$. To obtain at least $N$ acceptances with approximate probability $1-\delta$, use the standard normal distribution quantile $z={\Phi }^{-1}(1-\delta )$. The central limit theorem without continuity correction gives $n-MN\ge z\sqrt{n(M-1)}$. Solving this quadratic inequality in $\sqrt{n}$ gives the displayed threshold, rounded upward. It exceeds the average stopping cost $MN$ because it allows for fluctuations in the accepted count. For $M=1$, the count is deterministic and $n=N$ exactly. Exact coverage uses the binomial distribution tail rather than the approximation.

Conditional iid accepted values have the ordinary target-sample CLT at scale $\sqrt{N}$. Since $N/n\to 1/M$, the same estimator has asymptotic variance $M{\mathrm{Var}}_f\varphi$ at scale $\sqrt{n}$. The centered count has limiting variance $(1/M)(1-1/M)$. Any fixed convention on an empty output is asymptotically negligible.

With normalized densities $f,g$ and envelope $f\le Mg$, $M>1$, conditioning a proposal on rejection gives density $r=(Mg-f)/(M-1)$. It can be used as an importance sampling proposal only if it covers the relevant target support. If $Mg=f$ on a set of positive target mass, rejected draws never visit that set.

Adaptive rejection sampling builds a piecewise linear upper envelope for a differentiable log-concave probability density, samples from its piecewise exponential form, and accepts with the target-to-envelope ratio. Adding evaluated points improves the envelope without changing the target distribution. Initial tangent slopes must yield integrable tails. The accepted draws are exact samples, unlike a finite run of Markov chain Monte Carlo.