Survival of a random number of independent uniform return tests
ProvedCountingLLL.ReciprocalTest.random_uniform_survivalalgorithmsprobability
Let be a finite random nonnegative integer. Independently of , draw for each a uniform element from a set of elements with one distinguished value. The probability that each of the first draws avoids its distinguished value equals . This is the probabilistic survival identity used in the suppressed-return analysis of ReciprocalTest. Establishing that its adaptive execution has this product coupling is a separate task.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open CountingLLL.ReciprocalTest MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.random_uniform_survival {α : Type*} [MeasurableSpace α] (μ : Measure α) [IsProbabilityMeasure μ] (K : α → ℕ) (hK : Measurable K) : (μ.prod (Measure.infinitePi fun i : ℕ => uniformLaw (i+1))) {p : α × ((i : ℕ) → Fin (i+2)) | ∀ i < K p.1, (p.2 i).val ≠ 0} = ∫⁻ x, 1/(K x+1 : ℝ≥0∞) ∂μ := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, proof of Lemma 6.5, correctness, p. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf