Stopped-prefix independence for an almost-surely finite IID stopping time
ProvedCountingLLL.ContractedWalk.iid_ae_stopped_prefix_independentprobability
Let an IID Bernoulli tape have an Option-valued stopping time that is finite almost surely, with each event determined by the first bits. Let a natural-valued random variable be determined by the stopped prefix. Then that variable is independent of the post- increment tape. On the null nonstopping event the shifted tape uses an arbitrary fixed fallback. This gives the strong-Markov independence needed for first-hit segmentation.
Preamble
import Definitions.Def_CountingLLL_ContractedWalk open MeasureTheory ProbabilityTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.iid_ae_stopped_prefix_independent (p : ℝ≥0∞) (hp : p ≤ 1) (τ : Tape → Option ℕ) (R : Tape → ℕ)
(hτ : ∀ n ω ω', (∀ k < n, ω k = ω' k) → (τ ω = some n ↔ τ ω' = some n))
(hR : ∀ n ω ω', (∀ k < n, ω k = ω' k) → τ ω = some n → R ω = R ω')
(hfin : ∀ᵐ ω ∂tapeLaw p, τ ω ≠ none) :
IndepFun R (fun ω k => ω (k+(τ ω).getD 0)) (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