Contracted-walk harmonic expectation and generating function
ProvedCountingLLL.ContractedWalk.walk3_harmonic_pgfanalysisprobability
For , let be the upward-change count of the paper’s contracted walk started from level three, and let be the corresponding generating function from level one. Then
Preamble
import Definitions.Def_CountingLLL_ContractedGF open MeasureTheory CountingLLL.ContractedWalk open scoped ENNReal Interval BigOperators
Formal statement
theorem CountingLLL.ContractedWalk.walk3_harmonic_pgf (θ : ℝ) (hθ0 : 0 ≤ θ) (hθ : θ < 1/3) :
(∫ ω : Tape, ∑ k ∈ Finset.range (upwardCount ω 3), (1:ℝ)/(k+2) ∂tapeLaw (ENNReal.ofReal θ)) =
∫ z in (0:ℝ)..1, z*(1-(generatingFunction θ z)^3)/(1-z) := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, proof of Lemma 6.5, calls to O, p. 28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf