Stopped-prefix information is independent of the IID tail
ProvedCountingLLL.ContractedWalk.iid_stopped_prefix_independentprobability
Let be a finite stopping index on an IID Bernoulli tape, with determined by the bits before . Let a natural-valued variable also be determined by those stopped bits. Then is independent of the shifted tape beginning at . This is the strong-Markov independence ingredient for splitting the contracted walk into first-hit segments.
Preamble
import Definitions.Def_CountingLLL_ContractedWalk open MeasureTheory ProbabilityTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.iid_stopped_prefix_independent (p : ℝ≥0∞) (hp : p ≤ 1) (τ R : Tape → ℕ)
(hτ : ∀ n ω ω', (∀ k < n, ω k = ω' k) → (τ ω = n ↔ τ ω' = n))
(hR : ∀ n ω ω', (∀ k < n, ω k = ω' k) → τ ω = n → R ω = R ω') :
IndepFun R (fun ω k => ω (k+τ ω)) (tapeLaw 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