Operational Coin first return and exact oracle count
ProvedCountingLLL.ReciprocalTest.coin_first_return_and_costalgorithmsprobability
Start the operational local Coin procedure with unused entropy streams. Suppose the first oracle and fair-bit pairs are both false, and in the next pair at least one bit is true. Then Coin first returns after exactly oracle calls: there is a return state with that call count, and no earlier step is a return state. This pathwise result connects the geometric-trial description to the small-step machine.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open CountingLLL.ReciprocalTest
Formal statement
theorem CountingLLL.ReciprocalTest.coin_first_return_and_cost (ω : Entropy) (n : ℕ)
(h : ∀ k < n, ω.1 k = false ∧ ω.2.1 k = false)
(hexit : ω.1 n = true ∨ ω.2.1 n = true) :
∃ T, (((step ω)^[T] ({phase := .coinOracle .initial} : State)).phase = .initialCheck ∨
((step ω)^[T] ({phase := .coinOracle .initial} : State)).phase = .loop) ∧
((step ω)^[T] ({phase := .coinOracle .initial} : State)).oracleUsed = n+1 ∧
∀ t < T, ((step ω)^[t] ({phase := .coinOracle .initial} : State)).phase ≠ .initialCheck ∧
((step ω)^[t] ({phase := .coinOracle .initial} : State)).phase ≠ .loop := 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