Deferred decisions at a reveal-machine step
ProvedCountingLLL.RevealMachine.fresh_query_probabilityalgorithmsprobability
For a deterministic reveal machine running on an independent countable-valued array, consider an observable program-state event at a fixed step where a query is present. If, on that event, the queried coordinate has not previously been read and its designated coordinate event has probability , then the probability of together with that coordinate event is times the probability of . Coordinate laws may differ. This is a generic machine theorem; instantiating it for ReciprocalTest remains separate.
Preamble
import Definitions.Def_CountingLLL_RevealMachine open MeasureTheory ProbabilityTheory CountingLLL.RevealMachine open scoped ENNReal
Formal statement
theorem CountingLLL.RevealMachine.fresh_query_probability {σ ι α : Type*} [Countable ι] [DecidableEq ι]
[MeasurableSpace α] [Countable α] [MeasurableSingletonClass α]
(P : Program σ ι α) (initial : σ) (n : ℕ) (default : ι) (R : Set σ)
(κ : ι → Measure α) [∀ i, IsProbabilityMeasure (κ i)]
(A : ι → Set α) (hA : ∀ i, MeasurableSet (A i)) (p : ℝ≥0∞)
(hfresh : ∀ ω, (run P ω initial n).1 ∈ R → (P.query (run P ω initial n).1).isSome →
(P.query (run P ω initial n).1).getD default ∉ (run P ω initial n).2)
(hsame : ∀ ω, (run P ω initial n).1 ∈ R → (P.query (run P ω initial n).1).isSome →
κ ((P.query (run P ω initial n).1).getD default) (A ((P.query (run P ω initial n).1).getD default)) = p) :
(Measure.infinitePi κ) {ω | (run P ω initial n).1 ∈ R ∧ (P.query (run P ω initial n).1).isSome ∧
ω ((P.query (run P ω initial n).1).getD default) ∈ A ((P.query (run P ω initial n).1).getD default)} =
(Measure.infinitePi κ) {ω | (run P ω initial n).1 ∈ R ∧ (P.query (run P ω initial n).1).isSome} * p := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, Algorithm 6, pp. 27–28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf