First-stage mask probabilities satisfy the single-occurrence balance identity
ProvedStabilityDichotomies.Bijunctive.first_mask_single_flip_probability_balanceFix all first-stage inclusion decisions except one occurrence. Let and be the probabilities that the occurrence is respectively included and excluded while all the other decisions stay fixed. Then
For positive , this is the source change-of-measure ratio in the inside-first-stage deletion argument.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_BijunctiveLaw open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter Function StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.first_mask_single_flip_probability_balance {α : Type} [Fintype α] [DecidableEq α]
(ε : ℝ) (hε0 : 0 ≤ ε) (hε1 : ε ≤ 1) (m : α → Bool) (c : α) :
(ε / 2) * (Measure.pi (fun _ : α => unitPriorityMeasure)
(Set.univ.pi (fun i => if Function.update m c true i then Iic (1 - ε / 2) else Ioi (1 - ε / 2)))).toReal =
(1 - ε / 2) * (Measure.pi (fun _ : α => unitPriorityMeasure)
(Set.univ.pi (fun i => if Function.update m c false i then Iic (1 - ε / 2) else Ioi (1 - ε / 2)))).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, inside-first-stage deletion averaging.