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.

Metropolis–Hastings kernels — Examples

1 · Prerequisites

2 · Summary

These finite-state examples compute acceptance probabilities for a symmetric random walk, an independence proposal, a proposal with disconnected support, and a rejected self-transition. They verify the detailed-balance flow in each case and show concretely that invariance does not by itself ensure irreducibility or uniqueness.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

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

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.

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

A two-state independence sampler

Example

Assume AC. On the finite discrete space $X = {0, 1}$ , let $π (0) = 3 / 4$ , $π (1) = 1 / 4$ , and use the independence proposal $Q (x, {0}) = Q (x, {1}) = 1 / 2$ for both current states $x$ . Relative to counting measure, the common-density rule gives $α (0, 1) = 1 / 3$ and $α (1, 0) = 1$ . The transition matrix is $P = (\begin{array}{cc} 5 / 6 & 1 / 6 \\ 1 / 2 & 1 / 2 \end{array}),$ and the two off-diagonal target flows are both $1 / 8$ .

Verification

Given: AC, the two-state target and the state-independent proposal in the Example.

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

[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 every 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.

[F7] Metropolis–Hastings kernel: accepted proposal mass is retained at the proposed state and rejected mass is added to the current-state self-transition.

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

1.1F1F4given

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

1.2F2F3F5given

For each current state, the two proposal masses sum to one, so the row is a probability measure. Every event-evaluation function is measurable on the finite discrete space, hence [F3] and [F5] give a probability kernel. By [F2], target and proposal masses are their counting-measure densities.

2.1A1F6step 1.2algebra

The proposal masses cancel in [F6]. Hence $α (0, 1) = \min {1, (1 / 4) / (3 / 4)} = 1 / 3$ and $α (1, 0) = \min {1, (3 / 4) / (1 / 4)} = 1$ .

3.1F7step 2.1algebra

From state $0$ , the accepted mass to $1$ is $(1 / 2) (1 / 3) = 1 / 6$ and the remaining $5 / 6$ stays at $0$ . From state $1$ , the proposal to $0$ is accepted with mass $1 / 2$ , and the proposal to $1$ has mass $1 / 2$ . Applying [F7] gives the displayed matrix.

4.1F8step 3.1algebra∎

The off-diagonal flows are $π (0) P (0, 1) = (3 / 4) (1 / 6) = 1 / 8$ and $π (1) P (1, 0) = (1 / 4) (1 / 2) = 1 / 8$ . Diagonal flows agree with themselves, so [F8] gives reversibility and invariance.

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

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.

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

[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}$ .

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

Rejection creates a self-transition

Example

Assume AC. On the finite discrete space $X = {0, 1}$ , let $π (0) = 2 / 3$ , $π (1) = 1 / 3$ , and let the proposal deterministically switch to the other state. Then $α (0, 1) = 1 / 2$ and $α (1, 0) = 1$ , so $P = (\begin{array}{cc} 1 / 2 & 1 / 2 \\ 1 & 0 \end{array}) .$ The rejected proposal from state $0$ is recorded as a self-transition of probability $1 / 2$ .

Verification

Given: AC, the two-state target and the deterministic switch 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: a finite discrete space is standard Borel because its discrete metric is complete and the space is separable.

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

[F7] Metropolis–Hastings kernel: the rule adds rejected proposal mass to the current state's self-transition.

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

1.1F1F4given

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

1.2F2F3F5given

The proposal switches state with probability one in each row, so each row defines a probability measure. Every event-evaluation function is measurable on the finite discrete space, hence [F3] and [F5] give a probability kernel. By [F2], the displayed target and proposal masses are densities with respect to counting measure.

2.1A1F6step 1.2algebra

The reverse proposal masses are both one. Formula [F6] gives $α (0, 1) = \min {1, (1 / 3) / (2 / 3)} = 1 / 2$ and $α (1, 0) = \min {1, (2 / 3) / (1 / 3)} = 1$ . Thus the accepted mass from state $0$ to $1$ is $1 / 2$ , leaving rejected mass $1 / 2$ .

3.1F7F8step 2.1algebra∎

Applying the rejection rule [F7] gives $P (0, 0) = 1 / 2$ , $P (0, 1) = 1 / 2$ , $P (1, 0) = 1$ , and $P (1, 1) = 0$ . The off-diagonal target flows are both $1 / 3$ , so detailed balance holds and [F8] gives invariance.