ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedverified 2026-10-22 (gpt-6.1-sol)

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.

An exact invariant kernel can be biased over a short run

Example

Assume AC. Let $E = {- 1, + 1}$ with the discrete sigma-algebra $2^{E}$ , and let the target posterior $π$ assign mass $1 / 2$ to each state. For $0 < ε < 1 / 2$ , define $K_{ε} (x, A) : = (1 - ε) 1_{A} (x) + ε 1_{A} (- x) (x \in E, A \subseteq E) .$ Take $ε = 1 / 1000$ . The Ionescu--Tulcea construction supplies a time-homogeneous Markov chain on canonical path space with initial law $δ_{+ 1}$ and transition kernel $K_{ε}$ . Use this chain with its natural filtration, retain the next $N = 100$ draws, and set the bounded functional $f (x) = x$ . The target law $π$ is invariant for this exact kernel, but the expected reported average is $E [\frac{1}{100} \sum_{j = 1}^{100} X_{j}] = \frac{499}{100} (1 - {(\frac{499}{500})}^{100}) > 0 = π (f) .$ For the error ledger take each deterministic posterior stage to be $π$ ; then the invariant-kernel error is zero while the finite-run burn-in error is positive.

Example references

The invariant-kernel, burn-in, and Monte Carlo error components.

A probability kernel has probability rows and measurable event evaluations.

Invariance means $π K = π$ on every event.

The transition kernel gives the conditional one-step law.

Under AC, an initial law and a probability kernel give a canonical path-space Markov chain.

Conditional expectation is linear and preserves expectation.

Expectation is linear on integrable random variables.

The pathwise error budget is bounded by its adjacent-stage terms.

Levin, Peres, and Wilmer, §4.1, two-state chain

Facts & Assumptions

Given: The two-state target law, transition rule, deterministic initial state, and 100 retained draws in the Example.

[F1]

A probability kernel has probability-measure rows and measurable event evaluations. Measure kernel and probability kernel

[F2]

A probability law $π$ is invariant for $K$ when $\int K (x, A) π (d x) = π (A)$ for every event $A$ . Invariant and stationary distribution for a Markov kernel

[A1]

AC is assumed for conditional-expectation existence and the Ionescu--Tulcea chain construction. The Axiom of Choice

[F3]

For a time-homogeneous Markov chain, $P (X_{n + 1} \in A ∣ F_{n}) = K (X_{n}, A)$ almost surely. Time-homogeneous Markov chain with transition kernel

[F4]

The burn-in component is $∣ π_{K} (f) - E_{λ} {\overset{ˉ}{f}}_{b, N} ∣$ ; when the invariant target is $π$ , this is the expected finite-run bias in the Example. Posterior computation error budget

[F5]

The mean and conditional expectation of a bounded real random variable are finite. Moments, variance, and covariance on a probability space

[F6]

Under AC, the Ionescu--Tulcea construction gives a canonical path-space chain with the specified initial law and homogeneous transition kernel. Ionescu-Tulcea construction of a Markov chain

[F7]

Conditional expectation is linear and preserves expectation for integrable variables. Basic algebra and order properties of conditional expectation

[F8]

The expectation of a finite sum of integrable random variables is the sum of their expectations. The Lebesgue integral is linear on $L^{1} (μ)$

Verification

1.1A1F1F6given

Since $0 < ε < 1 / 2$ , each row assigns the nonnegative masses $1 - ε$ and $ε$ to the two states, and every subset is measurable; thus $K_{ε}$ is a probability kernel [F1]. Under AC [A1], apply [F6] to initial law $δ_{+ 1}$ and kernel $K_{ε}$ ; this supplies the canonical chain used in the Example.

2.1F1F2step 1.1givenalgebra

For either singleton ${x}$ , $π K_{ε} ({x}) = \frac{1}{2} (1 - ε) + \frac{1}{2} ε = \frac{1}{2} = π ({x}),$ so additivity on the two-state space gives $π K_{ε} = π$ by [F2].

2.2A1F3F5F7step 1.1givenalgebra

Put $λ_{0} : = 1 - 2 ε = 499 / 500$ . Summing the two conditional probabilities in [F3] against the values $+ 1$ and $- 1$ , conditional on $X_{n} = x$ , and using linearity [F7], $E [X_{n + 1} ∣ F_{n}] = (1 - ε) x + ε (- x) = λ_{0} x .$ Taking expectations by [F7] and using $X_{0} = 1$ gives $E X_{j} = λ_{0}^{j}$ for every $j \geq 1$ by induction.

3.1F4F8step 2.1step 2.2algebra∎

By [F8], $E [100^{- 1} \sum_{j = 1}^{100} X_{j}] = 100^{- 1} \sum_{j = 1}^{100} λ_{0}^{j} = \frac{499}{100} (1 - (499 / 500)^{100}) > 0$ . Since $π (f) = 0$ and $π$ is invariant by step 2.1, the kernel discrepancy vanishes, while [F4] identifies this positive difference as the burn-in component.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

43 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

David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov Chains and Mixing Times, second edition (standard reference, not scraped)