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.
A bivariate drift and minorization bound geometric coupling error
Statement
Let be a probability kernel, be -small for , and let . If , define residual probabilities on and assume If , set and impose no residual condition. Suppose is finite-valued and measurable and off . Then there are and such that a coupling of two -chains has a measurable split-success time , with on , and satisfies Consequently . For , the transition following the first visit to couples the chains.
Facts & Assumptions
Given: The kernel, one-step minorization, bivariate drift, finite residual bound, and in the Statement.
Measure kernel and probability kernel: the independent product and residual transition rules define probability transitions.
Total variation duality, kernel contraction, and coupling bound: for any coupling, total variation is bounded by the probability that the coupled variables differ.
Measurability of integration against a kernel: the residual expectations and stopped-chain expectations are measurable.
Finite products of probability kernels are probability kernels: independent coordinate transitions form the product probability kernel.
Canonical Markov chain on path space: the coupled kernel transitions have a canonical path realization under the stated AC convention.
Discrete strong Markov property: the attempt times obey the discrete strong Markov property.
The Axiom of Choice: the canonical path and split-transition construction uses AC as stated by [F6].
Proof
Given: The hypotheses and facts [F1]–[F7], with [A1].
Run the two coordinates independently until both lie in . At each such visit, use the minorization to toss a common Bernoulli() split: on success draw one shared state; on failure draw independently from . Let , with . Record success with a measurable binary flag and evolve synchronously thereafter, without testing equality before success. The shared transition is the pushforward of under ; this map is measurable on every measurable space. This construction has the required -marginals by [F1], [F2], and [F5].
Let count failed split transitions completed by time , with , and set . If , a visit to couples on the next transition, so the uncoupled contribution there is zero. If , off the conditional expectation of the next is at most ; on the uncoupled transition has probability and expected equal to . The definition of bounds its contribution after the extra factor by , since . Thus is a nonnegative supermartingale in both cases.
For any integer , the probability of at least failed attempts is at most . On the event with at most failures, and , so the supermartingale bound gives
Choose so and set . Both terms in step 3.1 are bounded by a constant times for some . Apply the coupling inequality [F3] to obtain the asserted geometric bound after increasing to cover the finite initial values of .
Depends on
- Canonical Markov chain on path space
- The Axiom of Choice
- Measure kernel and probability kernel
- Small-set minorization and geometric drift
- Total variation distance for probability laws
- Total variation duality, kernel contraction, and coupling bound
- Finite products of probability kernels are probability kernels
- Discrete strong Markov property
- Measurability of integration against a kernel
Used by
Dependency tree · two levels
31 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
- Gareth O. Roberts and Jeffrey S. Rosenthal, General State Space Markov Chains and MCMC Algorithms (standard reference, not scraped)
- Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier, Markov Chains (standard reference, not scraped)