A uniformizing correction step for finite permutation coupling
ProvedFinitePermutationCoupling.correction_stepcouplingfinite-probabilitypermutations
Let be a nonempty finite set of size , and let be a doubly stochastic real matrix on . Suppose for every pair . There is a doubly stochastic matrix satisfying
for every . For every fixed reference permutation and value ,
This is the probability of moving under the following correction: choose uniformly from ; with probability choose using the row , and swap with . The displayed inequality sums the mass of this correction branch; the other branch leaves unchanged.
The witness is . When , the cap is equivalent to . The multiplicative formulation also covers . 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.