ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

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

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

35 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Art B. Owen, Monte Carlo Theory, Methods and Examples, Chapter 4 §4.7 (standard reference, not scraped)
Computational Statistics with R, Chapter 6 §6.1 (standard reference, not scraped)