Deferred decisions with adaptive finite reveals and mixed coordinate laws
ProvedCountingLLL.ReciprocalTest.adaptive_fresh_observed_generalalgorithmsprobability
Let a nonanticipating rule observe a finite random set of an independent countable-valued array and select an unrevealed coordinate. For an observed event , if the selected coordinate event has probability on , then the probability of together with that event is . The laws and events may vary by coordinate. This applies to oracle bits, fair bits, and finite-uniform tests after embedding their values in a common countable space.
Preamble
import Mathlib open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.adaptive_fresh_observed_general {ι α : Type*} [Countable ι] [DecidableEq ι]
[MeasurableSpace α] [Countable α] [MeasurableSingletonClass α]
(κ : ι → Measure α) [∀ i, IsProbabilityMeasure (κ i)]
(A : ι → Set α) (hA : ∀ i, MeasurableSet (A i)) (p : ℝ≥0∞)
(revealed : (ι → α) → Finset ι) (next : (ι → α) → ι)
(hfresh : ∀ ω, next ω ∉ revealed ω)
(E : Set (ι → α))
(hsame : ∀ ω, ω ∈ E → κ (next ω) (A (next ω)) = p)
(hlocal : ∀ S a ω ω', (∀ i ∈ S, ω i = ω' i) →
((revealed ω = S ∧ next ω = a) ↔ (revealed ω' = S ∧ next ω' = a)))
(hobserved : ∀ S a ω ω', (∀ i ∈ S, ω i = ω' i) →
(revealed ω = S ∧ next ω = a) → (ω ∈ E ↔ ω' ∈ E)) :
(Measure.infinitePi κ) {ω | ω ∈ E ∧ ω (next ω) ∈ A (next ω)} =
(Measure.infinitePi κ) E * p := 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