# adaptive rejection sampling

(1.2 hours to learn)

## Summary

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.

## Context

This concept has the prerequisites:

- rejection sampling
- exponential distribution (The proposal distribution is piecewise exponential.)

## Goals

- 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)

## -Free-

→ Adaptive Rejection Sampling for Gibbs Sampling

Location:
Section 2.2

Other notes:

- Section 2.2 provides core information but the rest of the Section 2 provides context and deeper discussion of ARS

## -Paid-

→ Pattern Recognition and Machine Learning

A textbook for a graduate machine learning course, with a focus on Bayesian methods.

Location:
section 11.1.3

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

## -Free-

→ Wikipedia

## 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,