Contracted walk: number of changes before absorption
ProvedCountingLLL.ContractedWalk.stopped_change_boundcombinatoricsprobability
Consider the absorbed walk with upward steps of two and downward steps of one, started at level with . If it reaches zero, and is the initial counter plus the number of upward steps before absorption, then at most changes occur before absorption. This is a pathwise bound for the abstract contracted walk, not a coupling with the original algorithm.
Preamble
import Definitions.Def_CountingLLL_ContractedGF open CountingLLL.ContractedWalk
Formal statement
theorem CountingLLL.ContractedWalk.stopped_change_bound (ω : Tape) (j : ℕ) (hj : 1 ≤ j) (h : ∃ t, level ω (2*j-1) t = 0) : stopTime ω (2*j-1) ≤ 3 * (j + upwardCount ω (2*j-1)) := by sorry
Source
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, proof of Lemma 6.5, computational overhead, p. 28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf