Contracted walk upward-count generating-function recursion
ProvedCountingLLL.ContractedWalk.generating_function_recursionprobability
For the absorbed contracted walk from level one, let be the generating function of the number of upward steps before absorption. For and , the source claims .
Preamble
import Definitions.Def_CountingLLL_ContractedGF open MeasureTheory CountingLLL.ContractedWalk
Formal statement
theorem CountingLLL.ContractedWalk.generating_function_recursion (θ z : ℝ) (hθ0 : 0 ≤ θ) (hθ : θ < 1/3) (hz0 : 0 ≤ z) (hz1 : z ≤ 1) :
generatingFunction θ z = 1-θ+θ*z*(generatingFunction θ z)^3 := 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