Contracted-walk generating functions satisfy first-step recurrence
ProvedCountingLLL.ContractedWalk.first_step_expectationprobability
Let be the generating function of the number of upward moves before the contracted walk from level hits zero. For , and , the first-step recurrence is . This establishes the first-step part of the paper’s generating-function analysis.
Preamble
import Definitions.Def_CountingLLL_ContractedGF open MeasureTheory CountingLLL.ContractedWalk
Formal statement
theorem CountingLLL.ContractedWalk.first_step_expectation (θ z : ℝ) (hθ0 : 0 ≤ θ) (hθ : θ < 1/3)
(hz0 : 0 ≤ z) (hz1 : z ≤ 1) (i : ℕ) (hi : 0 < i) :
(∫ ω : Tape, z ^ upwardCount ω i ∂tapeLaw (ENNReal.ofReal θ)) =
(1-θ)*(∫ ω : Tape, z ^ upwardCount ω (i-1) ∂tapeLaw (ENNReal.ofReal θ)) +
θ*z*(∫ ω : Tape, z ^ upwardCount ω (i+2) ∂tapeLaw (ENNReal.ofReal θ)) := 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