Weighted upward changes form a harmonic sum
ProvedCountingLLL.ContractedWalk.weighted_increases_harmonicalgorithmsprobability
If the abstract contracted walk is absorbed, and is its total number of upward changes, then the total reciprocal-counter weight over upward changes equals , where is the initial counter. The statement holds pathwise for any initial level and counter.
Preamble
import Definitions.Def_CountingLLL_ContractedCost import Definitions.Def_CountingLLL_ContractedGF open MeasureTheory ProbabilityTheory CountingLLL.ContractedWalk open scoped ENNReal BigOperators
Formal statement
theorem CountingLLL.ContractedWalk.weighted_increases_harmonic (ω : Tape) (i j : ℕ)
(h : ∃ t, level ω i t = 0) :
weightedIncreases ω i j = ∑ k ∈ Finset.range (upwardCount ω i), (((j+k : ℕ) : ℝ≥0∞)⁻¹) := 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