Adaptive rejection sampling
Algorithms AIMech:AdaptiveRejectionSampling DRAFT
Aliases: ARS
The Gilks–Wild univariate rejection sampler that uses tangents to a concave log density as a piecewise-linear upper hull and chords as a lower hull, updating these bounds from evaluated proposals.
Identity Notes & Concept Scope
This record scopes ARS to the derivative-based tangent construction in Gilks and Wild (1992), for a fixed log-concave scalar target on a connected domain. Derivative-free envelope constructions and adaptive rejection Metropolis sampling are distinct variants requiring their own evidence. Exact conditional draws do not make successive joint Gibbs states independent. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 167 prior native IDs/names/aliases. Full-checkout searches in both worktrees included ignored and hidden files; the 15 lines in each were shared Tierney source-title references or an adaptive-rejection discovery lead, not matching records. Existing Gibbs, Metropolis-within-Gibbs, random-walk and independence Metropolis mechanisms were inspected to resolve specialization boundaries.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Write h=log g for a differentiable concave log density. At ordered support points evaluate h and h prime; tangent intersections define an upper hull u, and chords define a lower hull l, with l=−infinity outside the extreme support points. Initialize points so exp(u) is integrable; on unbounded tails this requires a positive leftmost slope and a negative rightmost slope. Draw x from normalized exp(u) and w uniformly on (0,1). Accept immediately if w≤exp(l(x)−u(x)); otherwise evaluate h(x) and h prime(x), accept if w≤exp(h(x)−u(x)), and incorporate the evaluated point into the hulls whether that full test accepted or rejected it. Repeat rejected trials. The conditional-on-history rejection argument gives the fixed target law for each output despite adaptation of the valid bounds.
⚠️ Curated Limitations & Negative Results
- Concavity of log g is essential for the tangent and chord bounds. Unimodality alone is insufficient, and non-log-concave targets are not covered by this construction.
- The displayed baseline assumes usable derivatives and connected scalar support. It does not assert validity for every nonsmooth density or a direct multivariate joint draw.
- Tail slopes and support endpoints must make the proposal integrable. Concentrated or skewed densities require numerical care.
- When a Gibbs conditional changes, hull values must be computed for that conditional; reusing stale density bounds is not justified.
- No universal evaluation savings or benchmark result is asserted. ARMS and its 1997 correction remain separate uninspected-method leads.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable target for this independent random-variate generator was found in the inspected pin. Its possible use inside a Gibbs sampler or Bayesian model is insufficient to force a process/model mapping. This is a bounded assessment of this AIO snapshot.
Search Scope: All 442 AIO CLASS labels/scoped synonyms and native identities; ignored-inclusive searches of both full checkouts. Semantic search covered sampling, Monte Carlo, Markov, Bayesian, probabilistic and mathematical-function descriptions; exact candidate targets and incident edges were inspected.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:MarkovChain
|
A stochastic sequence/model exported beneath Network, rather than an independent random-variate generation procedure. Embedding independent draws in a chain or an outer Gibbs algorithm does not establish the needed concept relation here. |
AIO:ProbabilisticGraphicalModel
|
Defines a graphical conditional-dependence task; no graphical factorization defines this generator. |
AIO:BayesianNetwork
|
A directed acyclic probabilistic model, not this sampling algorithm; use for a conditional distribution is incidental. |
AIO:MathematicalFunction
|
A generic rule assigning dependent-variable values is not a suitable identity or informative broader mapping for a randomized accept-reject procedure. |
AIO:SelectionAndSamplingBias
|
Describes selection-induced representativeness error, not exact generation from a specified target; shared sampling terminology is insufficient. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
W. R. Gilks, P. Wild
|
primary paper
full_text
|
ID: doi:10.2307/2347565
sha256:c88f55b2e19e…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T07:13:10Z
Updated: 2026-10-11T07:13:10Z
Source File:
data/curated/AdaptiveRejectionSampling.yaml