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 three-state random-walk Metropolis kernel

Example

Assume AC. Let $X = {0, 1, 2}$ with arithmetic modulo $3$ , target masses $π (0) = 1 / 2$ , $π (1) = 1 / 3$ , $π (2) = 1 / 6$ , and proposal probabilities $Q (x, x + 1) = Q (x, x - 1) = 1 / 2$ . This is a random walk on the three-cycle, and its proposal matrix is symmetric. The common-density Metropolis–Hastings rule gives $P = (\begin{array}{ccc} 1 / 2 & 1 / 3 & 1 / 6 \\ 1 / 2 & 1 / 4 & 1 / 4 \\ 1 / 2 & 1 / 2 & 0 \end{array}) .$ Its detailed-balance flows are $π (0) P (0, 1) = π (1) P (1, 0) = 1 / 6$ , $π (0) P (0, 2) = π (2) P (2, 0) = 1 / 12$ , and $π (1) P (1, 2) = π (2) P (2, 1) = 1 / 12$ ; hence $π$ is invariant by Metropolis–Hastings flow is reversible and invariant.

Verification

Given: AC, the finite target and the three-cycle 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: $P (x, y) = Q (x, y) α (x, y)$ for $y \neq x$ , and rejected mass is retained at $x$ .

[F8] Metropolis–Hastings flow is reversible and invariant: the Metropolis–Hastings joint flow is symmetric and its target is invariant.

1.1F1given

The finite discrete metric is complete and the three-point space is separable; its Borel sigma-algebra is therefore the full power set, so [F1] gives a standard-Borel state space.

1.2F2F4given

The target masses sum to one by [F4], and [F2] makes them densities with respect to counting measure.

1.3F3F5given

For each state, $x + 1$ and $x - 1$ are distinct modulo $3$ and the two proposal probabilities sum to one. Thus each row is a probability measure, and every event-evaluation function is measurable on the finite discrete space; [F3] and [F5] give a probability kernel.

2.1A1F6step 1.2step 1.3algebra

Since $Q (x, y) = Q (y, x) = 1 / 2$ for distinct states, [F6] gives $α (0, 1) = 2 / 3$ , $α (0, 2) = 1 / 3$ , $α (1, 0) = 1$ , $α (1, 2) = 1 / 2$ , and $α (2, 0) = α (2, 1) = 1$ . The rejected masses are $1 / 2$ at state $0$ , $1 / 4$ at state $1$ , and $0$ at state $2$ .

3.1F7step 2.1algebra

Multiplying each accepted proposal probability by its acceptance probability and retaining the rejected mass as in [F7] gives the three rows $(1 / 2, 1 / 3, 1 / 6)$ , $(1 / 2, 1 / 4, 1 / 4)$ , and $(1 / 2, 1 / 2, 0)$ . Each row sums to one.

4.1F8step 3.1algebra∎

Direct multiplication gives the three off-diagonal flow pairs $1 / 6$ , $1 / 12$ , and $1 / 12$ listed in the Example; diagonal flows are unchanged by transposition. Thus the joint flow is symmetric, and [F8] yields target invariance.

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.