Uniform positive chance of a counter decrease at a first Coin
ProvedCountingLLL.ReciprocalTest.suppressed_first_coin_decreaseformalizationprobability
At any first-Coin oracle phase with a positive first counter, the fully suppressed execution has probability at least B/2 of decreasing that counter within the next two atomic steps, even after restricting to an arbitrary finite history event. The inequality is stated in joint-probability form and includes histories of probability zero.
Preamble
import Definitions.Def_CountingLLL_ReciprocalSuppressedTransition open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.suppressed_first_coin_decrease (B : ℝ≥0∞) (hB : B ≤ 1) (n : ℕ)
(H : (Fin (n+1) → State) → Prop) (s : State)
(hs : s.phase = .coinOracle .first) (hi : 0 < s.i) :
entropyLaw B {ω | H (fun j => allSuppressedRun ω j.val) ∧ allSuppressedRun ω n = s} * (B/2) ≤
entropyLaw B {ω | H (fun j => allSuppressedRun ω j.val) ∧ allSuppressedRun ω n = s ∧
(allSuppressedRun ω (n+2)).i < s.i} := by sorrySource
Liu, Wang, Yin, Zhang, Zhou, A Counting and Sampling Lovász Local Lemma, STOC submission #442, Algorithm 6 and Lemma 6.5; progress ingredient toward almost-sure nonsticking.