adaptive rejection sampling

Adaptive rejection sampling (ARS) is a technique used to automatically choose and refine an envelope distribution, q(z), for rejection sampling of distribution p(z). ARS initially forms an envelope distribution, q(z), as a piecewise combination of intersecting line segments that outline p(z). These line segments are the tangents of log(p(z)) evaluated along a set of initial grid points and are guaranteed to enclose p(z) if p(z) is log-concave (the derivative of log(p(z)) is nonincreasing) -- this property holds for a large number of distributions. ARS then proceeds like rejection sampling, though if a sampled point is rejected at point x* then the tangent of log(p(x*)) is added to the envelope distributions, which shrinks the proposal distribution around the true distribution and leads to fewer rejected samples later on.