Count-mixture bound with an exceptional set
ProvedKSATSingleFlip.Connect.count_mixture_boundPartition an event by an integer-valued count. If on every count fiber its part outside an exceptional event has measure at most p times the fiber measure, then its total probability is at most p plus the probability of the exceptional event. This is the conditioning step for the Poisson-count case of Lemma 2.6.
Preamble
import Mathlib set_option autoImplicit false open MeasureTheory Set open scoped ENNReal
Formal statement
theorem KSATSingleFlip.Connect.count_mixture_bound {Ω : Type} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(N : Ω → ℕ) (hN : Measurable N) (E B : Set Ω) (hE : MeasurableSet E) (hB : MeasurableSet B)
(p : ℝ≥0∞)
(hfiber : ∀ j : ℕ, μ ((E \ B) ∩ N ⁻¹' {j}) ≤ μ (N ⁻¹' {j})*p) :
μ E ≤ p + μ B := by sorrySource
Wang–Yin–Yu–Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 2.6, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf