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.

Finite model error accumulates in a fixed chain

Example

Let $S = {0, 1}$ , let $N = 2$ , and start the true and learned chains at $δ_{0}$ . At both steps the true kernel is the identity. For a fixed $0 < ε < 1$ , the learned kernel sends $0$ to $1$ with probability $ε$ and leaves $0$ at $0$ otherwise, while it leaves $1$ at $1$ . Each step's largest row total-variation error is $ε$ , but after two learned steps the endpoint law assigns mass $2 ε - ε^{2}$ to $1$ , whereas the true endpoint law is $δ_{0}$ . The comparison is with the fixed two-step identity-kernel chain itself, so it has no discretization-error term, while the learned-kernel error is positive.

Example references

Finite-chain reverse-kernel error telescope: the endpoint bound sums the two uniform row errors and clamps the result at one.

Total variation distance for probability laws: total variation uses the event-supremum convention.

Facts & Assumptions

Given: $S = {0, 1}$ , the initial point mass $δ_{0}$ , two identity true kernels, and the two learned kernels in the Example. Verify each row error and the endpoint law.

[F1]

Total variation distance for probability laws: total variation is the supremum of absolute probability differences over events.

[F2]

Finite-chain reverse-kernel error telescope: the endpoint total variation is at most the initial error plus the sum of uniform row errors, clamped at one.

Verification

1.1givenF1algebra

At state $0$ , the true row is $δ_{0}$ and the learned row is $(1 - ε, ε)$ , so their event difference on ${1}$ is $ε$ ; at state $1$ the rows agree. Since these are the only two states, [F1] gives uniform row error exactly $ε$ at each step.

2.1givenF1step 1.1algebra

After one learned step the law is $(1 - ε, ε)$ . Since $1$ is absorbing and $0$ returns to $0$ with probability $1 - ε$ , after two steps its mass at $0$ is $(1 - ε)^{2}$ and its mass at $1$ is $1 - (1 - ε)^{2} = 2 ε - ε^{2}$ . The true identity chain remains $δ_{0}$ , so [F1] gives endpoint TV $2 ε - ε^{2} > 0$ .

3.1F2step 2.1algebra∎

For $ε = 1 / 4$ , the endpoint error is $7 / 16$ , while [F2] gives the valid bound $2 ε = 1 / 2$ . The example has no time-discretization term because the reference is the fixed two-step chain itself.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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