IID increments retain their law after a finite stopping time
ProvedCountingLLL.ContractedWalk.iid_stopping_tail_lawprobability
Let be a finite index on an IID Bernoulli increment stream such that the event is determined by bits strictly before . The shifted stream beginning at has the same IID product law as the original stream. This is a stopping-time tail-law ingredient for the first-hit decomposition in Lemma 6.5.
Preamble
import Definitions.Def_CountingLLL_ContractedWalk open MeasureTheory ProbabilityTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.iid_stopping_tail_law (p : ℝ≥0∞) (hp : p ≤ 1) (τ : Tape → ℕ)
(hτ : ∀ n ω ω', (∀ k < n, ω k = ω' k) → (τ ω = n ↔ τ ω' = n)) :
(tapeLaw p).map (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