Contracted walk pathwise balance
ProvedCountingLLL.ContractedWalk.path_balancealgorithmsprobability
For every finite path of the absorbed contracted walk, the current level plus the number of active changes equals the initial level plus three times the number of upward changes. This pathwise conservation identity supports the negative-drift bound.
Preamble
import Definitions.Def_CountingLLL_ContractedWalk open CountingLLL.ContractedWalk open scoped BigOperators
Formal statement
theorem CountingLLL.ContractedWalk.path_balance (ω : Tape) (i t : ℕ) :
level ω i t + (∑ k ∈ Finset.range t, if level ω i k = 0 then 0 else 1) =
i + 3*(∑ k ∈ Finset.range t, if level ω i k ≠ 0 ∧ ω k = true then 1 else 0) := 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