Lemma 1 — moment generating function tail bound
ProvedSigRoute.lemma_1interactive-proofsmartingale-concentrationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1routed-verificationsoundness-amplification
Let be a filtration and random variables with being -measurable. Let and satisfy
Then for and every ,
No independence is assumed: the may depend on the whole past. This is the adaptive Chernoff bound behind Theorem 14.
Formalization Note Rounds are 0-based: () is F (j+1)-measurable and is conditioned on F j.
Differences from the source:
- generalization: the σ-algebra of the first rounds of a routed session → an arbitrary filtration of an arbitrary probability space; reason: the session's filtration is an instance
- encoding: rounds conditioned on , answers → 0-based rounds conditioned on
F j, answers inBool; reason: relabelling; same instances - encoding: (extended-valued conditional expectation) → the same, plus
Integrable (fun ω => exp (λ * Y j ω)) μ; reason: Mathlib's conditional expectation of a non-integrable function is 0; in the paper the hypothesis forces , so only Lean's junk case is excluded - encoding: and conditional probabilities almost surely →
μ.real {ω | τ ≤ creditSum …}andcondProb(MathlibcondExpof the indicator), with∀ᵐ; reason: Lean convention; the events are measurable, so these are the paper's quantities
Preamble
import Mathlib
Formal statement
namespace SigRoute
open MeasureTheory
/-- Lemma 1 (Moment generating function tail bound) (Dumlu, Signal-Routed Two-Arm Verification, STOC 2027 submission manuscript (held version, sha256 d56b3b7a…), Lemma 1, p.4). Let `Y_1, …, Y_N ≥ 0` be
random variables with `Y_j` being `F_j`-measurable, and let `λ > 0` and `Λ ≥ 1` satisfy
`E[e^{λY_j} | F_{j−1}] ≤ Λ` for all `j`. Then for `S = ∑_j Y_j` and every `τ ∈ ℝ`,
`P[S ≥ τ] ≤ e^{−λτ} Λ^N`.
**Formalization Note** Rounds are 0-based: `Y j` (`j < N`) is `F (j+1)`-measurable and is conditioned on
`F j`. The filtration is an arbitrary filtration of an arbitrary probability space. The hypothesis
`Integrable (e^{λ Y_j})` is added because Mathlib's conditional expectation of a non-integrable function
is `0`, which would make the moment hypothesis vacuous; in the paper the hypothesis forces
`E e^{λY_j} ≤ Λ < ∞`. -/
theorem lemma_1 {Ω : Type*} {m : MeasurableSpace Ω} (μ : Measure Ω) [IsProbabilityMeasure μ]
(F : Filtration ℕ m) (N : ℕ) (Y : ℕ → Ω → ℝ)
(hY_nonneg : ∀ j < N, ∀ ω, 0 ≤ Y j ω)
(hY_meas : ∀ j < N, Measurable[F (j + 1)] (Y j))
(lam Λ : ℝ) (hlam : 0 < lam) (hΛ : 1 ≤ Λ)
(hint : ∀ j < N, Integrable (fun ω => Real.exp (lam * Y j ω)) μ)
(hmgf : ∀ j < N, condExp (F j) μ (fun ω => Real.exp (lam * Y j ω)) ≤ᵐ[μ] fun _ => Λ)
(τ : ℝ) :
μ.real {ω | τ ≤ ∑ j ∈ Finset.range N, Y j ω} ≤ Real.exp (-lam * τ) * Λ ^ N := by sorry
end SigRoute
Source
Dumlu, Signal-Routed Two-Arm Verification, STOC 2027 submission manuscript (held version, sha256 d56b3b7a…), Lemma 1, p.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.