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$.

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$.

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.