Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A uniformizing correction step for finite permutation coupling

Proved
FinitePermutationCoupling.correction_step

by dmilosch · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

couplingfinite-probabilitypermutations

Let α\alphaα be a nonempty finite set of size mmm, and let PPP be a doubly stochastic real matrix on α\alphaα. Suppose (m−1)P(u,v)≤1(m-1)P(u,v)\le 1(m−1)P(u,v)≤1 for every pair u,vu,vu,v. There is a doubly stochastic matrix TTT satisfying

(1−1m)P(u,v)+1mT(u,v)=1m\left(1-\frac1m\right)P(u,v)+\frac1m T(u,v)=\frac1m(1−m1​)P(u,v)+m1​T(u,v)=m1​

for every u,vu,vu,v. For every fixed reference permutation hhh and value vvv,

1m2∑u,zT(u,z) 1[swap⁡(h(u),z)(v)≠v]≤2m2.\frac1{m^2}\sum_{u,z}T(u,z)\,\mathbf1[\operatorname{swap}(h(u),z)(v)\ne v]\le\frac2{m^2}.m21​u,z∑​T(u,z)1[swap(h(u),z)(v)=v]≤m22​.

This is the probability of moving vvv under the following correction: choose uuu uniformly from α\alphaα; with probability 1/m1/m1/m choose zzz using the row T(u,⋅)T(u,\cdot)T(u,⋅), and swap h(u)h(u)h(u) with zzz. The displayed inequality sums the mass of this correction branch; the other branch leaves vvv unchanged.

The witness is T(u,v)=1−(m−1)P(u,v)T(u,v)=1-(m-1)P(u,v)T(u,v)=1−(m−1)P(u,v). When m≥2m\ge2m≥2, the cap is equivalent to P(u,v)≤1/(m−1)P(u,v)\le1/(m-1)P(u,v)≤1/(m−1). The multiplicative formulation also covers m=1m=1m=1. This is a local kernel theorem, not the construction of the complete cycle-conditioned coupling or its sequential probability law.

Preamble
import Mathlib.Tactic
import Mathlib.Analysis.Convex.DoublyStochasticMatrix

set_option autoImplicit false
Formal statement
namespace FinitePermutationCoupling

open scoped BigOperators

theorem correction_step {α : Type*} [Fintype α] [DecidableEq α] [Nonempty α] (P : Matrix α α ℝ)
    (hP : P ∈ doublyStochastic ℝ α)
    (hcap : ∀ u v, ((Fintype.card α : ℝ) - 1) * P u v ≤ 1) :
    ∃ T : Matrix α α ℝ,
      T ∈ doublyStochastic ℝ α ∧
      (∀ u v, (1 - 1 / (Fintype.card α : ℝ)) * P u v +
        (1 / (Fintype.card α : ℝ)) * T u v = 1 / (Fintype.card α : ℝ)) ∧
      ∀ (h : Equiv.Perm α) (v : α),
        (1 / (Fintype.card α : ℝ) ^ 2) *
            (∑ u, ∑ z, if Equiv.swap (h u) z v ≠ v then T u z else 0) ≤
          2 / (Fintype.card α : ℝ) ^ 2 := by
  sorry

end FinitePermutationCoupling
Source
Carolan, Childs, Coudron, Gilani, Miloschewsky, Podder, Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard, https://arxiv.org/html/2611.05912v1#S4.SS4. Proof of Lemma 4.13: the residual kernel after equation (76), the uniform mixture in step 2, and the conditional correction-move estimate 2/r² before equation (77). This abstracts the one-step calculation to an arbitrary nonempty finite doubly stochastic matrix, including the singleton case.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me