Weighted contracted-walk cost has finite expectation
ProvedCountingLLL.ContractedWalk.weighted_cost_finiteprobability
For , a contracted walk started at level with initial counter has expected total reciprocal-counter change weight at most . In particular, the source weighted-change quantity is finite.
Preamble
import Definitions.Def_CountingLLL_ContractedCost open MeasureTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.weighted_cost_finite (θ : ℝ) (hθ0 : 0 ≤ θ) (hθ1 : θ < 1/3) (i j : ℕ) (hj : 1 ≤ j) :
expectedWeightedChanges (ENNReal.ofReal θ) i j ≤ ENNReal.ofReal ((i : ℝ)/(1-3*θ)) := 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