Operational return probability is the supremum of finite-step probabilities
ProvedCountingLLL.ReciprocalTest.return_probability_supalgorithmsprobability
For either output bit, the operational ReciprocalTest return probability equals the supremum over of the probability that the machine is in the corresponding done state after steps. Done states are absorbing, so the finite-step events are increasing. This connects the finite-step state-distribution recursion to eventual output probabilities.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open MeasureTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.return_probability_sup (B : ℝ≥0∞) (b : Bool) :
entropyLaw B {ω | Returns ω b} = ⨆ n : ℕ, entropyLaw B {ω | (run ω n).phase = .done b} := 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