Operational Coin return-one probability
ProvedCountingLLL.ReciprocalTest.coin_operational_probabilityalgorithmsprobability
For , execute the initial Coin call of Algorithm 6 in its small-step machine, using independent oracle, fair-bit and uniform-draw streams. The probability that the call returns one is exactly . This is the source’s Coin output claim applied to the actual operational semantics.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.coin_operational_probability (B : ℝ) (hB0 : 0 ≤ B) (hB1 : B ≤ 1) :
entropyLaw (ENNReal.ofReal B)
{ω | ∃ t, ((step ω)^[t] ({phase := .coinOracle .initial} : State)).phase = .initialCheck} =
ENNReal.ofReal (2*(1-B)/(2-B)) := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC 2027 #442, Algorithm 6 and proof of Lemma 6.5, PDF p. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf