Contracted walk upward-step probability
ProvedCountingLLL.ReciprocalTest.contracted_up_probabilityalgorithmsprobability
Let independent calls to Coin return one with probability . In one walk iteration, two ones cause an upward change, a one followed by zero is a self-loop, and an initial zero causes a downward change. After suppressing any number of self-loops, the probability of an upward change is . The theorem models the fresh Coin outcomes as IID Boolean pairs; the construction of the full recursive walk from the small-step machine remains separate.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.contracted_up_probability (u : ℝ) (hu0 : 0 ≤ u) (hu1 : u ≤ 1) :
let ν := (oracleLaw (ENNReal.ofReal (1-u))).prod (oracleLaw (ENNReal.ofReal (1-u)))
let μ := Measure.infinitePi fun _ : ℕ => ν
μ {ω : ℕ → Bool × Bool | ∃ n, (∀ i < n, ω i = (true,false)) ∧ ω n = (true,true)} =
ENNReal.ofReal (u^2/(1-u+u^2)) := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC 2027 #442, proof of Lemma 6.5, PDF p. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf