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.

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]

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

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)