Contracted walk absorption and expected change count
ProvedCountingLLL.ContractedWalk.absorption_and_expected_changesalgorithmsprobability
For , the absorbed walk that moves down by one with probability and up by two with probability reaches zero almost surely. Starting from level , its expected number of changes is at most . This is the source’s contracted-walk hitting-time estimate.
Preamble
import Definitions.Def_CountingLLL_ContractedWalk open MeasureTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.absorption_and_expected_changes (θ : ℝ) (hθ0 : 0 ≤ θ) (hθ : θ < 1/3) (i : ℕ) :
tapeLaw (ENNReal.ofReal θ) {ω | ∃ t, level ω i t = 0} = 1 ∧
expectedChanges (ENNReal.ofReal θ) i ≤ ENNReal.ofReal ((i : ℝ) / (1-3*θ)) := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC 2027 #442, proof of Lemma 6.5, PDF p. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf