ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge 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 proposal with disconnected support

Example

Assume AC. On the finite discrete space $X = {0, 1, 2}$ , let $π$ be uniform and propose deterministically $0 \mapsto 1$ , $1 \mapsto 0$ , and $2 \mapsto 2$ . The proposal has no transitions between ${0, 1}$ and ${2}$ . Every proposal with positive mass has a reverse proposal of the same mass, so the Metropolis acceptance probability is one and $P = Q$ . The target $π$ is invariant, but the distinct probability $δ_{2}$ is also invariant; the chain cannot move from $0$ or $1$ to $2$ .

Verification

Given: AC, the uniform target and the deterministic proposal in the Example.

[A1] The Axiom of Choice: AC states that every family of nonempty sets has a choice function.

[F1] Standard Borel spaces and Polish spaces are separable completely metrizable spaces: the discrete metric on a finite set is complete and separable, every subset is open, and the Borel sigma-algebra is the full power set; the definition therefore makes it standard Borel.

[F2] Counting measure on an arbitrary set and Counting measure is a measure: counting measure is a positive measure and assigns mass one to each singleton. Since this state space is finite, its total counting measure is finite and the one-set cover makes it sigma-finite by Finite, sigma-finite, and semifinite measures. Thus the target and proposal masses are densities with respect to counting measure.

[F3] Transition matrices and n-step probabilities: the entry $Q (x, y)$ is $Q (x, {y})$ .

[F4] Probability measures and probability spaces: a probability measure has total mass one.

[F5] Measure kernel and probability kernel: a probability kernel is a measurable family of probability measures with mass one at each current state. Each row's nonnegative singleton masses sum to one, so it defines a probability measure by finite addition; all event evaluations are measurable because the finite discrete state space has the full power-set sigma-algebra.

[F6] The common-density Metropolis–Hastings ratio: a common-density version $α_{c d}$ is $\min {1, π (y) Q (y, x) / [π (x) Q (x, y)]}$ when the forward mass is positive and is chosen as $1$ when that mass is zero.

[F7] Metropolis–Hastings kernel: the algorithm accepts using the common-flow ratio and retains rejected proposals at the current state.

[F8] Metropolis–Hastings flow is reversible and invariant: the constructed kernel leaves its target invariant.

1.1F1F4given

The target masses sum to one, and the discrete metric makes the finite state space standard Borel.

1.2F2F3F5given

Every row of the proposal matrix has one entry equal to one and the rest zero, so it defines a probability measure. Every event-evaluation function is measurable on the finite discrete space, hence [F3] and [F5] give a probability kernel; [F2] identifies its entries and target masses with counting-measure densities.

2.1A1F6step 1.2algebra

The positive proposal transitions are $0 \leftrightarrow 1$ and $2 \to 2$ . In each case the forward and reverse proposal masses and target masses agree, so [F6] gives acceptance probability one.

3.1F7F8step 2.1algebra∎

Hence [F7] gives $P = Q = (\begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array}) .$ The matrix is a permutation matrix, so its column sums are one and the uniform target is invariant; [F8] gives the same conclusion from reversibility. The point mass $δ_{2}$ is invariant because state $2$ never leaves. The two invariant probabilities differ, and no transition path connects ${0, 1}$ to ${2}$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

47 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.