Proof of `Haeupler–Saha–Srinivasan Theorem 2.2`
groundedproofs/Lax41Proofs/HaeuplerSahaSrinivasanTheorem22.lean · lax-41
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
At the first stage where the observed event is true, adjoin it as a distinguished root to the execution history. The resulting proper witness tree has no further copy of the root and all of its other labels lie in . The witness-tree lemma bounds the probability of every such tree, and the branching-process sum is exactly the local-lemma neighborhood product. The output event is a subset of the event that the observation was true at some stage.