Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

A bivariate drift and minorization bound geometric coupling error

Statement

Let Q be a probability kernel, D be (1,ϵ,ν)-small for Q, and let 0<a<1. If 0<ϵ<1, define residual probabilities Rx=(Q(x,⋅)−ϵν)/(1−ϵ) on D and assume B≥max⁡{1,(1−ϵ)sup⁡(x,y)∈D2Rx⊗Ry(h)/a}<∞. If ϵ=1, set B=1 and impose no residual condition. Suppose h:X2→[1,∞) is finite-valued and measurable and Q⊗Q h≤ah off D2. Then there are M<∞ and 0<r<1 such that a coupling of two Q-chains has a measurable split-success time T, with Xn=Yn on {T≤n}, and satisfies Pr⁡x,y(T>n)≤Mh(x,y)rn. Consequently ∥Qn(x,⋅)−Qn(y,⋅)∥TV≤Mh(x,y)rn. For ϵ=1, the transition following the first visit to D2 couples the chains.

Facts & Assumptions

Given: The kernel, one-step minorization, bivariate drift, finite residual bound, and h≥1 in the Statement.

[F1]

Small-set minorization and geometric drift: on D, Q(x,⋅)≥ϵν.

[F2]

Measure kernel and probability kernel: the independent product and residual transition rules define probability transitions.

[F3]

Total variation duality, kernel contraction, and coupling bound: for any coupling, total variation is bounded by the probability that the coupled variables differ.

[F4]

Measurability of integration against a kernel: the residual expectations and stopped-chain expectations are measurable.

[F5]

Finite products of probability kernels are probability kernels: independent coordinate transitions form the product probability kernel.

[F6]

Canonical Markov chain on path space: the coupled kernel transitions have a canonical path realization under the stated AC convention.

[F7]

Discrete strong Markov property: the attempt times obey the discrete strong Markov property.

[A1]

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].

1.1F1F2F4F5F6F7A1given

Run the two coordinates independently until both lie in D. At each such visit, use the minorization to toss a common Bernoulli(ϵ) split: on success draw one shared ν state; on failure draw independently from Rx,Ry. Let T=inf⁡{k+1:the split at time k succeeds}, with inf⁡∅=∞. Record success with a measurable binary flag and evolve synchronously thereafter, without testing equality before success. The shared transition is the pushforward of Q(Xk,⋅) under z↦(z,z); this map is measurable on every measurable space. This construction has the required Q-marginals by [F1], [F2], and [F5].

2.1F1F2F4F7A1step 1.1

Let Nk count failed split transitions completed by time k, with N0=0, and set Zk=a−kB−Nkh(Xk,Yk)1{T>k}. If ϵ=1, a visit to D2 couples on the next transition, so the uncoupled contribution there is zero. If 0<ϵ<1, off D2 the conditional expectation of the next h is at most ah; on D2 the uncoupled transition has probability 1−ϵ and expected h equal to Rx⊗Ry(h). The definition of B bounds its contribution after the extra factor B−1 by ah(x,y), since h≥1. Thus (Zk) is a nonnegative supermartingale in both cases.

3.1step 2.1algebra

For any integer j≥1, the probability of at least j failed attempts is at most (1−ϵ)j. On the event T>k with at most j−1 failures, h≥1 and BNk≤Bj−1, so the supermartingale bound gives Pr⁡(T>k)≤(1−ϵ)j+akBj−1h(x,y).

4.1F3step 3.1algebra∎

Choose θ>0 so aBθ<1 and set j=max⁡(1,⌊θk⌋). Both terms in step 3.1 are bounded by a constant times rk for some r<1. Apply the coupling inequality [F3] to obtain the asserted geometric bound after increasing M to cover the finite initial values of k.

Depends on

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