TheoremStatement: Literature-sourcedProof: 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.

Finite-chain reverse-kernel error telescope

Statement

Let $S$ be a finite nonempty state space and let $N \geq 1$ . For each $j = 1, \dots, N$ , let $Q_{j}$ and $P_{j}$ be probability kernels on $S$ , used in reverse order from level $j$ to level $j - 1$ . Starting from probability vectors $μ_{N}, ν_{N}$ , define $μ_{j - 1} = μ_{j} Q_{j}$ and $ν_{j - 1} = ν_{j} P_{j}$ . If $TV (μ_{N}, ν_{N}) \leq ε_{i n i t}$ and $\sup_{z \in S} TV (Q_{j} (z, \cdot), P_{j} (z, \cdot)) \leq ε_{j} (1 \leq j \leq N),$ where $ε_{i n i t}, ε_{1}, \dots, ε_{N} \in [0, 1]$ , then $TV (μ_{0}, ν_{0}) \leq \min {1, ε_{i n i t} + \sum_{j = 1}^{N} ε_{j}} .$ Here $TV (u, v) = \sup_{A \subseteq S} ∣ u (A) - v (A) ∣$ .

Statement references

Total variation distance for probability laws: for probability laws, total variation is the supremum of absolute event-probability differences.

Measure kernel and probability kernel: a probability kernel has probability-law rows; on $S$ its action is matrix multiplication.

Facts & Assumptions

Given: The finite state space, the $N$ pairs of probability kernels, the initial probability vectors, and all stated total-variation bounds. Prove the endpoint bound.

[F1]

Total variation distance for probability laws: $TV (u, v) = \sup_{A \subseteq S} ∣ u (A) - v (A) ∣$ and lies in $[0, 1]$ for probability laws.

[F2]

Total variation duality, kernel contraction, and coupling bound: applying the same probability kernel to two input laws cannot increase their total-variation distance.

[F3]

Uniform row error bounds mixture-kernel error: a uniform row-wise total-variation error $ε_{j}$ gives $TV (ρ Q_{j}, ρ P_{j}) \leq ε_{j}$ for every input law $ρ$ .

[F4]

Measure kernel and probability kernel: each $Q_{j}$ and $P_{j}$ row is a probability law.

Proof

1.1givenF1F2F3F4algebra

Fix $j$ and $A \subseteq S$ . Insert the intermediate measure $ν_{j} Q_{j}$ and use the ordinary triangle inequality for real numbers on the two event differences. The first difference is at most $TV (μ_{j}, ν_{j})$ by [F2], and the second is at most $ε_{j}$ by [F3]. Taking the supremum over $A$ by [F1] gives $TV (μ_{j - 1}, ν_{j - 1}) \leq TV (μ_{j}, ν_{j}) + ε_{j}$ .

2.1givenstep 1.1algebra

Apply step 1.1 successively for $j = N, N - 1, \dots, 1$ . The intermediate distances telescope, so $TV (μ_{0}, ν_{0}) \leq TV (μ_{N}, ν_{N}) + \sum_{j = 1}^{N} ε_{j} \leq ε_{i n i t} + \sum_{j = 1}^{N} ε_{j}$ .

3.1F1step 2.1algebra∎

Since both endpoint vectors are probability laws, [F1] gives $TV (μ_{0}, ν_{0}) \leq 1$ . Combining this with step 2.1 yields the stated minimum, including the cases $N = 1$ , zero kernel errors, and a sum at least one.

Depends on

Used by

Finite model error accumulates in a fixed chain Example

Dependency tree · two levels

8 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 and Yuval Peres, Markov Chains and Mixing Times, second edition (standard reference, not scraped)