Fixed-count tail on an independent count fiber
ProvedKSATSingleFlip.Connect.fixed_count_independent_fiberSuppose an integer-valued clause count is independent of a vector of j independent clause marks, and the observable changes by at most L under inserting a mark. On the count-j fiber, its lower-tail probability is at most the probability of that fiber multiplied by the fixed-count concentration bound from Lemma 2.6. The theorem states this in a joint probability space without conditioning on a possibly null fiber.
Preamble
import Mathlib open MeasureTheory ProbabilityTheory Set open scoped ENNReal set_option autoImplicit false
Formal statement
theorem KSATSingleFlip.Connect.fixed_count_independent_fiber {Ω A : Type} [MeasurableSpace Ω] [MeasurableSpace A]
(P : Measure Ω) [IsProbabilityMeasure P] (D : Measure A) [IsProbabilityMeasure D]
(N : Ω → ℕ) (j : ℕ) (hj : 1 ≤ j) (Q : Ω → Fin j → A)
(hQ : Measurable Q) (hlaw : Measure.map Q P = Measure.pi (fun _ : Fin j => D))
(hind : IndepFun N Q P) (F : List A → ℝ)
(hF : Measurable (fun x : Fin j → A => F (List.ofFn x)))
(L u : ℝ) (hL : 1 ≤ L) (hu : 0 < u)
(hins : ∀ (xs : List A) (i : ℕ) (a : A), |F (xs.insertIdx i a)-F xs| ≤ L) :
P ({ω | N ω = j} ∩ {ω | F (List.ofFn (Q ω)) ≤
(∫ x, F (List.ofFn x) ∂(Measure.pi (fun _ : Fin j => D)))-u}) ≤
P {ω | N ω = j} * ENNReal.ofReal (Real.exp (-(u^2)/(2*(j:ℝ)*L^2))) := 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