Fresh independent bit after any finite set of reveals
ProvedCountingLLL.ReciprocalTest.fresh_coordinate_eventalgorithmsprobability
Consider a countable family of independent Boolean coordinates, possibly with different one-coordinate laws. If an event depends only on a finite set of coordinates and , then
This supports deferred decisions for interleaved oracle and fair-bit reveals in the reciprocal-test machine.
Preamble
import Mathlib open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.fresh_coordinate_event {ι : Type*} [Countable ι] [DecidableEq ι]
(κ : ι → Measure Bool) [∀ i, IsProbabilityMeasure (κ i)]
(S : Finset ι) (a : ι) (ha : a ∉ S) (E : Set (ι → Bool))
(hE : ∀ ω ω', (∀ i ∈ S, ω i = ω' i) → (ω ∈ E ↔ ω' ∈ E)) :
(Measure.infinitePi κ) {ω | ω ∈ E ∧ ω a = true} =
(Measure.infinitePi κ) E * κ a {true} := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, Algorithm 6 and proof of Lemma 6.5, pp. 27–28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf