Rejection sampling
Algorithms AIMech:RejectionSampling DRAFT
Aliases: Accept-reject sampling
A random-variate generation algorithm that draws proposals from a normalized envelope dominating an unnormalized target and accepts each with the target-to-envelope ratio, yielding independent target draws with fresh independent random trials.
Identity Notes & Concept Scope
This is ordinary accept-reject generation with a valid global envelope. A rejected candidate is discarded, not recorded as a repeated chain state. The method differs from Metropolis acceptance, rejection-driven Metropolis proposals, importance weighting and selective filtering of model answers. The inspected primary source presents the scalar density case. 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
For a nonnegative target g with finite positive integral, choose an integrable envelope g_u with g_u(x)≥g(x) everywhere on the target support and sample x from g_u/integral(g_u). Independently draw w uniformly on (0,1); accept x if w≤g(x)/g_u(x), otherwise discard the trial and repeat. An optional lower bound 0≤g_l≤g allows early acceptance when the same w≤g_l(x)/g_u(x), avoiding evaluation of g. Fresh independent trials produce independent accepted draws from normalized g. The target normalizing constant is not required for the acceptance ratio.
⚠️ Curated Limitations & Negative Results
- A valid dominating envelope and an exact sampler for its normalized distribution are required. Clipping an invalid envelope ratio at one does not preserve the intended independent-sample law.
- An envelope with excessive mass can make acceptance rare. No universal efficiency, dimensional scaling or bound on the number of trials is claimed.
- The optional squeezing bound must be valid everywhere it is used; it is an evaluation shortcut, not a replacement target.
- Numerical approximation, finite precision and inaccurate envelope sampling can change the output distribution. Log concavity is not required by ordinary rejection sampling itself.
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/RejectionSampling.yaml