Fresh walk increment is independent of every prefix event
ProvedCountingLLL.ContractedWalk.prefix_event_independentprobability
Let be an independent Bernoulli tape with success probability . If an event is completely determined by the coordinates before time , then
This allows current walk level and accumulated counter to be used together when analyzing the next fresh upward step.
Preamble
import Definitions.Def_CountingLLL_ContractedWalk open MeasureTheory ProbabilityTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.prefix_event_independent (p : ℝ≥0∞) (hp : p ≤ 1) (t : ℕ) (E : Set Tape)
(hE : ∀ ω ω', (∀ k < t, ω k = ω' k) → (ω ∈ E ↔ ω' ∈ E)) :
tapeLaw p {ω | ω ∈ E ∧ ω t = true} = tapeLaw p E * p := 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