ReciprocalTest transition masses sum to one
ProvedCountingLLL.ReciprocalTest.transitionMass_sumalgorithmsprobability
For , the one-step transition masses of the operational ReciprocalTest sum to one from every state. Querying steps push a probability measure forward through a deterministic successor map; silent steps have a single successor.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTransition open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.transitionMass_sum (B : ℝ≥0∞) (hB : B ≤ 1) (s : State) :
(∑' s' : State, transitionMass B s s') = 1 := 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