Coin first-exit event equals its operational success event
ProvedCountingLLL.ReciprocalTest.coin_success_iffalgorithmsprobability
Start the initial Coin call in Algorithm 6 with fresh oracle and fair-bit streams. It returns one exactly when, for some , the first oracle and corresponding fair bits are all zero and the next oracle answer is one. This identifies the IID first-exit event with the operational small-step execution, path by path, without assuming termination.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open CountingLLL.ReciprocalTest
Formal statement
theorem CountingLLL.ReciprocalTest.coin_success_iff (ω : Entropy) : (∃ t, ((step ω)^[t] ({phase := .coinOracle .initial} : State)).phase = .initialCheck) ↔ ∃ n, (∀ k < n, ω.1 k = false ∧ ω.2.1 k = false) ∧ ω.1 n = true := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC 2027 #442, Algorithm 6 lines 1–7, PDF p. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf