Survival probability for independent uniform return tests
ProvedCountingLLL.ReciprocalTest.independent_uniform_survivalalgorithmsprobability
For each , independently draw a uniform value from a set of elements with one distinguished element. The probability that none of the first draws selects its distinguished element is . These independent uniform tests are the tests associated with successive counter values in the paper’s suppressed-return analysis; linking their indexed draws to the machine execution remains separate.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open CountingLLL.ReciprocalTest MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.independent_uniform_survival (n : ℕ) : (Measure.infinitePi fun i : ℕ => uniformLaw (i+1)) {ω : (i : ℕ) → Fin (i+2) | ∀ i < n, (ω i).val ≠ 0} = 1/(n+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