Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 3 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 3 also cleared it.

Rejection sampling — Examples

1 · Prerequisites

2 · Summary

Examples

A two-point target and proposal give a bounded density ratio with an exact acceptance rate and proposal count. A countable Pareto-type pair has normalized masses but an unbounded target-to-proposal ratio, so no finite envelope works. A second two-point calculation uses unnormalized masses to verify the $Z_{f} / (c Z_{g})$ acceptance formula and the normalized accepted law.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A lighter-tailed proposal has no finite rejection envelope

Example

On $N = {0, 1, 2, \dots}$ with counting measure, put $f (0) = g (0) = 0$ and for $n \geq 1$ define $f (n) = \frac{1}{n (n + 1)}, g (n) = \frac{4}{n (n + 1) (n + 2)} .$ Both are probability masses, but their ratio $f (n) / g (n) = (n + 2) / 4$ for $n \geq 1$ is unbounded. Thus this lighter-tailed proposal has no finite rejection envelope for the target.

Facts & Assumptions

[A1]

The sample space is $N$ with counting measure. The displayed target and proposal masses are nonnegative and vanish at $0$ .

[F1]

Rejection sampling: a finite rejection envelope requires $f (n) \leq c g (n)$ at every point outside a common counting-null set.

[F2]

Counting measure on an arbitrary set, Counting measure is a measure, and Counting-measure integration is a nonnegative series: counting measure assigns each set its cardinality, so its only null set is empty; integration of a nonnegative function against it is the nonnegative series of its point masses.

[F3]

The reals form a totally ordered field and The Cauchy-sequence reals have the least-upper-bound property: $R$ is a complete ordered field.

[F4]

For every $ε > 0$ in a complete ordered field there is a natural $n \geq 1$ with $1 / n < ε$ : for every $ε > 0$ some positive integer $m$ satisfies $1 / m < ε$ .

[F5]

Inverses of positives are positive, and reciprocation reverses order and Canonical naturals are positive and strictly increasing: reciprocation reverses positive order, and the canonical naturals are positive and strictly increasing.

[F6]

Limits and Cauchy sequences of reals: a real sequence tends to $x$ when every positive rational tolerance eventually bounds its distance from $x$ .

[F7]

Every complete ordered field is Archimedean: for every real $x$ there is a positive integer $n > x$ .

Verification

Given: The two mass functions in the Example, counting measure on $N$ , and the real number field.

1.1A1F2F3F4F5F6algebra

The partial sums telescope: $\sum_{n = 1}^{N} f (n) = 1 - \frac{1}{N + 1}$ and $\sum_{n = 1}^{N} g (n) = 1 - \frac{2}{(N + 1) (N + 2)}$ . For any positive rational $ε$ , [F4] applied to $ε / 2$ supplies $m$ with $1 / m < ε / 2$ ; for all $N + 1 \geq m$ , [F5] gives $1 / (N + 1) \leq 1 / m < ε / 2$ and $2 / ((N + 1) (N + 2)) \leq 2 / (N + 1) \leq 2 / m < ε$ . Thus both remainders tend to zero by [F6], and [F2] gives total masses $1$ .

2.1A1F1F2F7step 1.1algebra∎

At each $n \geq 1$ , $\frac{f (n)}{g (n)} = \frac{n + 2}{4}$ . For any finite proposed envelope $c > 0$ , [F7] gives a positive integer $n > 4 c$ , so $f (n) / g (n) = (n + 2) / 4 > c$ . Since [F2] says the only counting-null set is empty, no common null exception can remove these points. This contradicts the required envelope in [F1]; the pair has no finite rejection envelope.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A bounded target-to-proposal density ratio

Example

On $S = {a, b}$ with counting measure, let the target masses be $f (a) = 1 / 4, f (b) = 3 / 4$ and the proposal masses be $g (a) = g (b) = 1 / 2$ . The density ratio is bounded by $c = 3 / 2$ . Rejection sampling has acceptance probability $2 / 3$ , returns the target law, and has expected proposal count $3 / 2$ .

Facts & Assumptions

[A1]

The sample space is the two-point set $S = {a, b}$ with counting measure. The listed target and proposal functions are nonnegative.

[F1]

Counting measure on an arbitrary set, Counting measure is a measure, The integral of a nonnegative simple function, and The nonnegative integral agrees with the simple integral on simple functions: on this finite space, the integral of a nonnegative function is the sum of its two values.

[F2]

Rejection sampling has the target acceptance law: normalized shapes with envelope constant $c$ have accepted density $f$ and acceptance probability $1 / c$ .

[F3]

Expected proposal count under a finite rejection envelope: for normalized target and proposal densities, the expected count is $c$ .

[F4]

Rejection sampling: for normalized shapes, a proposal $y$ with $g (y) > 0$ is accepted when $U \leq f (y) / (c g (y))$ .

Verification

Given: The target and proposal masses in the Example, and the algorithm's ideal independent proposal-uniform draws.

1.1A1F1algebra

By [F1], $\int f d # = 1 / 4 + 3 / 4 = 1$ and $\int g d # = 1 / 2 + 1 / 2 = 1$ . The ratios are $f (a) / g (a) = 1 / 2$ and $f (b) / g (b) = 3 / 2$ , so $c = 3 / 2$ is a finite envelope and is the least such constant.

2.1F2F3F4step 1.1algebra∎

Applying [F2] gives the accepted masses $(1 / 4, 3 / 4)$ and acceptance probability $1 / c = 2 / 3$ ; [F3] gives expected proposal count $c = 3 / 2$ . The two-point calculation is exact: accepted submasses are $1 / 2 \cdot (1 / 3) = 1 / 6$ at $a$ and $1 / 2 \cdot 1 = 1 / 2$ at $b$ , totaling $2 / 3$ ; the factors follow from [F4], and dividing by $2 / 3$ gives $(1 / 4, 3 / 4)$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Rejection sampling with unnormalized finite masses

Example

On $S = {a, b}$ with counting measure, take unnormalized target masses $\tilde{f} (a) = 2, \tilde{f} (b) = 1$ and proposal shape $\tilde{g} (a) = \tilde{g} (b) = 1$ . With $c = 2$ , the envelope holds and $Z_{f} = 3, Z_{g} = 2$ . Rejection sampling accepts with probability $3 / 4$ , returns normalized target masses $(2 / 3, 1 / 3)$ , and uses $4 / 3$ proposals on average.

Facts & Assumptions

[A1]

The sample space is the two-point set $S = {a, b}$ with counting measure. The displayed shapes are nonnegative.

[F1]

[F2]

Rejection sampling has the target acceptance law: unnormalized shapes with envelope constant $c$ have acceptance probability $Z_{f} / (c Z_{g})$ and accepted masses $\tilde{f} / Z_{f}$ .

[F3]

Expected proposal count under a finite rejection envelope: the expected count is the reciprocal of the acceptance probability.

[F4]

Rejection sampling: for unnormalized shapes, a proposal $y$ with $\tilde{g} (y) > 0$ is accepted when $U \leq \tilde{f} (y) / (c \tilde{g} (y))$ .

Verification

Given: The shapes and envelope constant in the Example, counting measure, and the ideal independent proposal-uniform draws.

1.1A1F1algebra

By [F1], $Z_{f} = 2 + 1 = 3$ and $Z_{g} = 1 + 1 = 2$ . Pointwise, $\tilde{f} (a) = 2 = 2 \tilde{g} (a)$ and $\tilde{f} (b) = 1 \leq 2 \tilde{g} (b)$ , so $c = 2$ is a valid finite envelope.

2.1F2step 1.1algebra

Applying [F2] gives acceptance probability $p = Z_{f} / (c Z_{g}) = 3 / 4$ and accepted masses $(\tilde{f} (a) / Z_{f}, \tilde{f} (b) / Z_{f}) = (2 / 3, 1 / 3)$ .

3.1F3F4step 2.1algebra∎

Direct finite enumeration checks the same result: the proposal is uniform on ${a, b}$ ; by [F4], $a$ is always accepted and $b$ is accepted with probability $1 / 2$ . The accepted submasses are therefore $1 / 2$ and $1 / 4$ , their sum is $3 / 4$ , and normalization gives $(2 / 3, 1 / 3)$ . By [F3] the expected count is $1 / p = 4 / 3$ .

Rejection sampling — Examples

1 · Prerequisites

2 · Summary

Examples

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A lighter-tailed proposal has no finite rejection envelope

Example

Facts & Assumptions

Verification

A bounded target-to-proposal density ratio

Example

Facts & Assumptions

Verification

Rejection sampling with unnormalized finite masses

Example

Facts & Assumptions

Verification

Sources