LemmaStatement: 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.

Uniform row error bounds mixture-kernel error

Statement

Let $S$ be a finite nonempty set and let $Q$ and $P$ be probability kernels on $S$ , meaning that each row is a probability vector. For probability vectors $u, v$ on $S$ , use $TV (u, v) = \sup_{A \subseteq S} ∣ u (A) - v (A) ∣$ , where $u (A) = \sum_{x \in A} u (x)$ . If $\sup_{x \in S} TV (Q (x, \cdot), P (x, \cdot)) \leq ε$ for $0 \leq ε \leq 1$ , then every probability vector $μ$ on $S$ satisfies $TV (μ Q, μ P) \leq ε,$ where $(μ Q) (A) = \sum_{x \in S} μ (x) Q (x, A)$ and similarly for $μ P$ .

Statement references

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

Measure kernel and probability kernel: each kernel row is a probability measure; on finite power-set spaces this is a row-stochastic matrix.

Facts & Assumptions

Given: A finite nonempty set $S$ , probability kernels $Q, P$ on $S$ , a probability vector $μ$ on $S$ , and $0 \leq ε \leq 1$ with the stated uniform row bound. Prove $TV (μ Q, μ P) \leq ε$ .

[F1]

Total variation distance for probability laws: for probability laws $u, v$ , $TV (u, v) = \sup_{A} ∣ u (A) - v (A) ∣$ .

[F2]

Measure kernel and probability kernel: every row $Q (x, \cdot)$ and $P (x, \cdot)$ is a probability law.

Proof

1.1givenF1F2algebra

Fix $A \subseteq S$ . By [F2] and the finite mixture formulas, $∣ (μ Q) (A) - (μ P) (A) ∣ = ∣ \sum_{x \in S} μ (x) (Q (x, A) - P (x, A)) ∣ \leq \sum_{x \in S} μ (x) ∣ Q (x, A) - P (x, A) ∣ .$ Each summand's event difference is bounded by its row total variation, so the right side is at most $\sum_{x} μ (x) ε = ε$ .

2.1F1step 1.1∎

Taking the supremum over all $A \subseteq S$ in step 1.1 and applying [F1] gives $TV (μ Q, μ P) \leq ε$ .

Depends on

Used by

Finite-chain reverse-kernel error telescope Theorem

Dependency tree · two levels

5 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)