Operational ReciprocalTest next query has its marginal law
ProvedCountingLLL.ReciprocalTest.operational_query_freshalgorithmsprobability
Under the original independent entropy law, fix a step and an exact operational ReciprocalTest state whose next query is coordinate . The probability of reaching and seeing the next encoded value in any set is the probability of reaching times the prescribed marginal probability of at . This proves the one-step deferred-decisions property for oracle bits, fair bits, and finite-uniform draws; it does not itself prove the full output or expected-cost formula.
Preamble
import Definitions.Def_CountingLLL_ReciprocalEncodedLaw open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest CountingLLL.RevealMachine open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.operational_query_fresh (B : ℝ≥0∞) (hB : B ≤ 1) (n : ℕ) (s : State) (a : ReadIndex)
(ha : readIndex s = some a) (U : Set ℕ) :
entropyLaw B {ω | CountingLLL.ReciprocalTest.run ω n = s ∧ entropyCode ω a ∈ U} =
entropyLaw B {ω | CountingLLL.ReciprocalTest.run ω n = s} * readLaw B a U := 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