First-exit probability for independent trials
ProvedCountingLLL.RandomRAM.iid_first_exitprobability
Let independent trials have common law , and let and be disjoint measurable events. Continue while trials fall in , and succeed when the first trial outside lies in . Then the success probability is , interpreted in extended nonnegative reals. This identity supplies the geometric-race calculation for the local Coin procedure of Algorithm 6.
Preamble
import Theorems.Thm_CountingLLL_RandomRAM_reciprocal_expected_cost open MeasureTheory ProbabilityTheory open scoped ENNReal BigOperators
Formal statement
theorem CountingLLL.RandomRAM.iid_first_exit {β : Type} [MeasurableSpace β] (ν : Measure β) [IsProbabilityMeasure ν]
(S T : Set β) (hS : MeasurableSet S) (hT : MeasurableSet T) (hst : Disjoint S T) :
let μ := Measure.infinitePi fun _ : ℕ => ν
μ {ω : ℕ → β | ∃ n, (∀ i < n, ω i ∈ S) ∧ ω n ∈ T} = ν T / (1 - ν S) := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC 2027 #442, Algorithm 6, PDF p. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf