A measurable shared seed bounds Wasserstein distance by bit-disagreement probabilities
ProvedStabilityDichotomies.Solvability.wasserstein_le_measurable_seed_bit_changesLet and be measurable maps from a common probability space into assignments on a finite set of Boolean variables. Their output laws satisfy
This is the shared-randomness coupling bound needed for the continuous priority, cutoff, and shift seeds in Theorem 4.9.
Preamble
import Definitions.Def_StabilityDichotomies_Solvability_Stability open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Function StabilityDichotomies.Solvability
Formal statement
theorem StabilityDichotomies.Solvability.wasserstein_le_measurable_seed_bit_changes {V Ω : Type} [Fintype V] [MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] (f g : Ω → V → Bool)
(hf : Measurable f) (hg : Measurable g) :
letI : IsProbabilityMeasure (Measure.map f μ) := Measure.isProbabilityMeasure_map hf.aemeasurable
letI : IsProbabilityMeasure (Measure.map g μ) := Measure.isProbabilityMeasure_map hg.aemeasurable
wasserstein ((Measure.map f μ).toPMF) ((Measure.map g μ).toPMF) ≤
∑ v : V, (μ {ω | f ω v ≠ g ω v}).toReal := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, coupling and Hamming-distance bound.