Source weighted-change expectation is a harmonic expectation
ProvedCountingLLL.ContractedWalk.cost_harmonic_expectationalgorithmsprobability
For , let be the expected sum of reciprocal counters over all changes in the abstract contracted walk starting at level three and counter two, and let be its number of upward changes before absorption. Then
The equality is in extended nonnegative reals and is the probabilistic reduction used in the source oracle-cost argument.
Preamble
import Definitions.Def_CountingLLL_ContractedGF import Definitions.Def_CountingLLL_ContractedCost open MeasureTheory CountingLLL.ContractedWalk open scoped BigOperators ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.cost_harmonic_expectation (θ : ℝ) (hθ0 : 0 ≤ θ) (hθ1 : θ < 1/3) :
expectedWeightedChanges (ENNReal.ofReal θ) 3 2 * ENNReal.ofReal θ =
∫⁻ ω, ∑ k ∈ Finset.range (upwardCount ω 3), (((2+k : ℕ) : ℝ≥0∞)⁻¹) ∂tapeLaw (ENNReal.ofReal θ) := 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