ReciprocalTest next query has its marginal law
ProvedCountingLLL.ReciprocalTest.encoded_query_freshalgorithmsprobability
Under the independent encoded input law, at any fixed step and on any exact state whose next query is coordinate , the event that the next value belongs to a set has probability equal to the state probability times the marginal probability assigned to at . This covers adaptive oracle bits, fair bits and uniform draws. Equality with the original entropy law and the full execution distribution remain separate.
Preamble
import Definitions.Def_CountingLLL_ReciprocalEncodedLaw open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest CountingLLL.RevealMachine open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.encoded_query_fresh (B : ℝ≥0∞) (hB : B ≤ 1) (n : ℕ) (s : State) (a : ReadIndex)
(ha : readIndex s = some a) (U : Set ℕ) :
encodedEntropyLaw B {x | (CountingLLL.RevealMachine.run revealProgram x initial n).1 = s ∧ x a ∈ U} =
encodedEntropyLaw B {x | (CountingLLL.RevealMachine.run revealProgram x initial n).1 = 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