Bernoulli mask marginal under occurrence reindexing and deletion
ProvedStabilityDichotomies.Approximability.bernoulli_mask_restrictioncombinatoricsprobability
Let a finite original occurrence set be bijective to an optional index of a finite retained set. For any real p and any real-valued function of the retained Boolean mask, summing against the original Bernoulli product weights gives exactly the Bernoulli-p weighted sum on the retained set. In the range 0 ≤ p ≤ 1 this states that deleting one coordinate and reindexing preserves the independent retention law. This supplies the probability marginal needed for the source deletion coupling.
Preamble
import Mathlib noncomputable section open scoped Classical BigOperators
Formal statement
theorem StabilityDichotomies.Approximability.bernoulli_mask_restriction {α β : Type} [Fintype α] [Fintype β]
(e : α ≃ Option β) (p : ℝ) (g : (β → Bool) → ℝ) :
(∑ x : α → Bool, (∏ j : α, if x j then p else 1-p) *
g (fun k => x (e.symm (some k)))) =
∑ y : β → Bool, (∏ k : β, if y k then p else 1-p) * g y := by sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, deletion coupling in proof of Theorem 4.3, p. 17, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf