Countable-state distribution recursion for operational ReciprocalTest
ProvedCountingLLL.ReciprocalTest.operational_distribution_stepalgorithmsprobability
Under the original entropy law with , let be the explicitly defined one-step transition mass of the operational ReciprocalTest. For every step and state $s',
The sum is over all operational states. The theorem proves the finite-step distribution recursion; solving its eventual return and expected-cost equations is separate.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTransition open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest CountingLLL.RevealMachine open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.operational_distribution_step (B : ℝ≥0∞) (hB : B ≤ 1) (n : ℕ) (s' : State) :
entropyLaw B {ω | CountingLLL.ReciprocalTest.run ω (n+1) = s'} =
∑' s : State, entropyLaw B {ω | CountingLLL.ReciprocalTest.run ω n = s} * transitionMass B 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