A uniform finite label transfers independent event probabilities to a finite average
ProvedStabilityDichotomies.Bijunctive.uniform_label_independent_event_probabilityLet be a uniformly distributed finite label and let be independent of . Given a measurable event for each label ,
This transfers conditional uniform cutoff-order events and independent exponential shifts to the finite combinatorial bounds in the proof of Theorem 4.9.
Preamble
import Mathlib open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Function
Formal statement
theorem StabilityDichotomies.Bijunctive.uniform_label_independent_event_probability {Ω Δ ι : Type}
[MeasurableSpace Ω] [MeasurableSpace Δ] [Fintype ι]
(μ : Measure Ω) (ν : Measure Δ) [IsProbabilityMeasure μ] [IsProbabilityMeasure ν]
(label : Ω → ι) (hlabel : ∀ i, MeasurableSet {ω | label ω = i})
(huniform : ∀ i, μ.real {ω | label ω = i} = 1 / Fintype.card ι)
(E : ι → Set Δ) (hE : ∀ i, MeasurableSet (E i)) :
((μ.prod ν) {z : Ω × Δ | z.2 ∈ E (label z.1)}).toReal =
(1 / (Fintype.card ι : ℝ)) * ∑ i : ι, ν.real (E i) := 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, conditional ordering and independent shifts.