Contracted walk level is independent of its next increment
ProvedCountingLLL.ContractedWalk.next_bit_independentalgorithmsprobability
At any time , the event that the contracted walk has not yet hit zero is independent of the fresh upward-step bit. Thus the probability of an active upward step equals the active probability multiplied by .
Preamble
import Definitions.Def_CountingLLL_ContractedWalk open MeasureTheory ProbabilityTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.next_bit_independent (p : ℝ≥0∞) (hp : p ≤ 1) (i t : ℕ) :
tapeLaw p {ω | level ω i t ≠ 0 ∧ ω t = true} = tapeLaw p {ω | level ω i t ≠ 0} * p := 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