Operational query-step transition law
ProvedCountingLLL.ReciprocalTest.operational_transition_lawalgorithmsprobability
For the original ReciprocalTest entropy law, fix a current state with queried coordinate and a candidate next state The joint probability of being in at step and in at step is the state probability times the marginal probability of the queried values which make the deterministic step reach These are one-step laws; eventual return and total expected cost are separate.
Preamble
import Definitions.Def_CountingLLL_ReciprocalEncodedLaw open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest CountingLLL.RevealMachine open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.operational_transition_law (B : ℝ≥0∞) (hB : B ≤ 1) (n : ℕ)
(s s' : State) (a : ReadIndex) (ha : readIndex s = some a) :
entropyLaw B {ω | CountingLLL.ReciprocalTest.run ω n = s ∧ CountingLLL.ReciprocalTest.run ω (n+1) = s'} =
entropyLaw B {ω | CountingLLL.ReciprocalTest.run ω n = s} *
readLaw B a {v | step (uniformEntropy v) s = s'} := 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