ReciprocalTest final output-probability calculation
ProvedCountingLLL.ReciprocalTest.source_accuracy_algebrainequalitiesprobability
For , define , , and . Then the expression for the output-one probability obtained from the paper’s generating-function and integral identities equals . This verifies their final algebraic calculation; the stochastic generating-function identities themselves remain to be proved.
Preamble
import Mathlib
Formal statement
theorem CountingLLL.ReciprocalTest.source_accuracy_algebra (B : ℝ) (hB0 : 0 < B) (hB1 : B < 1) :
let u := 2*(1-B)/(2-B)
let θ := u^2/(1-u+u^2)
let I := 1-θ/(2*(1-θ))
1-((1-u)*I + u*(I-1+θ)/θ)/2 = 1/(2*B) := 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