adaptive rejection sampling

(1.2 hours to learn)


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.


This concept has the prerequisites:


  • Be able to implement the adaptive rejection sampling algorithm.
  • What is the advantage compared to standard rejection sampling?

Core resources (read/watch one of the following)


Adaptive Rejection Sampling for Gibbs Sampling
Location: Section 2.2
Authors: Walter R Gilks,Pascal Wild
Other notes:
  • Section 2.2 provides core information but the rest of the Section 2 provides context and deeper discussion of ARS


Supplemental resources (the following are optional, but you may find them useful)

See also

  • Adaptive Metropolis rejection sampling is a generalization of ARS that is applicable when the distribution is not log-concave
  • ARS can be performed by computing secants (rather than tangents) and thus a can be accomplished without computing the derivative of the log density; see Gilks, W. R. (1992) Derivative-free adaptive rejection sampling for Gibbs sampling. Bayesian Statistics 4,