Operational Coin expected oracle-call count
ProvedCountingLLL.ReciprocalTest.operational_coin_expected_callsalgorithmsprobability
For , start the operational local Coin procedure on the independent oracle and fair-bit entropy streams. The expected number of oracle calls up to its first return is exactly , interpreted in the extended nonnegative reals. This concerns one local Coin call, not the total number of calls made by the full ReciprocalTest.
Preamble
import Definitions.Def_CountingLLL_CoinCost open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.operational_coin_expected_calls (B : ℝ) (hB0 : 0 ≤ B) (hB1 : B ≤ 1) :
(∫⁻ ω, coinOracleCost ω ∂entropyLaw (ENNReal.ofReal B)) = ENNReal.ofReal (2/(2-B)) := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, Algorithm 6 and proof of Lemma 6.5, pp. 27–28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf