ReciprocalTest fresh inputs conditional on the complete history
ProvedCountingLLL.ReciprocalTest.operational_history_freshformalizationprobability
Fix an execution time and state of the operational ReciprocalTest algorithm. For any event determined by the entire finite state history, if the current state selects an entropy coordinate, then the next encoded value of that coordinate retains its original marginal law conditional on the history and current state. The identity is unnormalized and remains valid when the conditioning event has probability zero.
Preamble
import Definitions.Def_CountingLLL_ReciprocalEncodedLaw open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.operational_history_fresh (B : ℝ≥0∞) (hB : B ≤ 1) (n : ℕ) (s : State) (a : ReadIndex)
(ha : readIndex s = some a) (H : (Fin (n+1) → State) → Prop) (U : Set ℕ) :
entropyLaw B {ω | H (fun j => CountingLLL.ReciprocalTest.run ω j.val) ∧
CountingLLL.ReciprocalTest.run ω n = s ∧ entropyCode ω a ∈ U} =
entropyLaw B {ω | H (fun j => CountingLLL.ReciprocalTest.run ω j.val) ∧
CountingLLL.ReciprocalTest.run ω n = s} * readLaw B a U := by sorrySource
Liu, Wang, Yin, Zhang, Zhou, A Counting and Sampling Lovász Local Lemma, STOC submission #442, §6.2, Lemma 6.5. This is an adaptive fresh-input lemma for the operational model, needed for a full execution coupling.