Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 10.2 — adaptive Gaussian lower bound E0[T]≥2 kl(1−δ,δ)Ψ(H,ν)/γ2\mathbb E_0[T]\ge 2\,\mathrm{kl}(1-\delta,\delta)\Psi(H,\nu)/\gamma^2E0​[T]≥2kl(1−δ,δ)Ψ(H,ν)/γ2

Open
FairReplay.Supplement.theorem_10_2

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

fairness-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1sequential-testing

In the Gaussian delta-oracle model with known standard deviations νv>0\nu_v>0νv​>0, margin γ>0\gamma>0γ>0 and δ∈(0,1/2)\delta\in(0,1/2)δ∈(0,1/2), let (π,T,ψ)(\pi,T,\psi)(π,T,ψ) be an adaptive tester whose type-I error at the null instance θ≡0\theta\equiv 0θ≡0 is at most δ\deltaδ, whose type-II error is at most δ\deltaδ at every θ\thetaθ with ∣θu−θv∣≥γ|\theta_u-\theta_v|\ge\gamma∣θu​−θv​∣≥γ on some edge of HHH, and whose expected number of calls at θ≡0\theta\equiv0θ≡0 is finite. Then

E0[T] ≥ 2 kl(1−δ,δ)γ2 Ψ(H,ν),\mathbb E_0[T]\ \ge\ \frac{2\,\mathrm{kl}(1-\delta,\delta)}{\gamma^2}\,\Psi(H,\nu),E0​[T] ≥ γ22kl(1−δ,δ)​Ψ(H,ν),

with kl(x,y)=xlog⁡xy+(1−x)log⁡1−x1−y\mathrm{kl}(x,y)=x\log\frac xy+(1-x)\log\frac{1-x}{1-y}kl(x,y)=xlogyx​+(1−x)log1−y1−x​.

This is the adaptive null-side converse to Theorem 10.1: no adaptive allocation of oracle calls beats the graph allocation by more than confidence constants.

Differences from the source:

  • generalization: δ-correct: type I ≤ δ under every null θ (θ_u = θ_v on all edges) → type I ≤ δ assumed only at θ ≡ 0; reason: the paper's δ-correctness implies the Lean hypothesis, so the Lean theorem specializes to the paper's
  • encoding: an adaptive (δ-correct) tester → a triple (π, T, ψ) on the published sequential-sampling model: possibly randomized adaptive policy, stopping time of the transcript filtration (⊤ = never stops), decision measurable for the stopped σ-algebra; type II counts non-stopping as an error; reason: the tester model of the published base mission; randomized policies contain the deterministic ones, so the class is at least the paper's
  • encoding: Gaussian delta-oracle calls at the vertices of H → the tester may call any vertex of Fin n; reason: calls outside V+(H) carry no information about H's edges; allowing them only enlarges the tester class
Preamble
import Mathlib
import Definitions.Def_BanditTrajectory
import Definitions.Def_bernoulliRelativeEntropy
import Definitions.Def_FairReplay_expectedRounds
import Definitions.Def_FairReplay_Supplement_gaussianModel
import Definitions.Def_FairReplay_Supplement_gaussAlloc

open MeasureTheory
Formal statement
namespace FairReplay.Supplement

/-- **Theorem 10.2 (Adaptive lower bound)** (Sah, Zhang, Lian, *Testing Fairness of Evolving Software under Uncertainty*, STOC 2027 submission (manuscript of 2026-11-03, sha256 e23940a0…), Theorem 10.2, eq. (18), p.12 (PDF p.14), with §3,
p.3): "For δ ∈ (0, 1/2), every adaptive δ-correct tester with finite expected stopping time (measured
in Gaussian delta-oracle calls) has, on the null instance θ ≡ 0, E0[T] ≥ 2kl(1 − δ, δ)/γ² Ψ(H, ν). (18)"

Let `H` be a residual graph on `Fin n`, `ν_v > 0`, `γ > 0` and `δ ∈ (0, 1/2)`. Every adaptive tester
`(π, T, ψ)` on the Gaussian delta-oracle model that rejects with probability at most `δ` at `θ ≡ 0`,
fails to reject with probability at most `δ` at every `θ` with `|θ_u − θ_v| ≥ γ` on some edge of `H`,
and has `E₀[T] < ∞`, satisfies `E₀[T] ≥ 2 kl(1 − δ, δ) Ψ(H, ν)/γ²`.

**Formalization Note** Testers are adaptive, possibly randomized policies over all vertices of `Fin n`
(one call = one round), with a stopping time `T` of the transcript filtration and a decision measurable
for the stopped σ-algebra; a run that never stops counts as an error under an alternative. Only
type I at `θ ≡ 0` is assumed, which the paper's δ-correctness implies. `kl` is
`BanditAlgorithm.bernoulliRelativeEntropy`. -/
theorem theorem_10_2 {n : ℕ} (H : SimpleGraph (Fin n)) [DecidableRel H.Adj] (ν : Fin n → ℝ)
    (hν : ∀ v, 0 < ν v) (γ : ℝ) (hγ : 0 < γ) (δ : ℝ) (hδ : 0 < δ) (hδ2 : δ < 1 / 2)
    (π : BanditAlgorithm.BanditPolicy n) (T : (ℕ → Fin n × ℝ) → ℕ∞)
    (ψ : (ℕ → Fin n × ℝ) → Bool) (hT : BanditAlgorithm.IsBanditStoppingTime T)
    (hψ : Measurable[hT.measurableSpace] ψ)
    (hI : BanditAlgorithm.banditTrajMeasure (gaussianModel 0 ν) π {ω | T ω < ⊤ ∧ ψ ω = true} ≤
      ENNReal.ofReal δ)
    (hII : ∀ θ : Fin n → ℝ, (∃ u v, H.Adj u v ∧ γ ≤ |θ u - θ v|) →
      BanditAlgorithm.banditTrajMeasure (gaussianModel θ ν) π {ω | ¬ (T ω < ⊤ ∧ ψ ω = true)} ≤
        ENNReal.ofReal δ)
    (hfin : expectedRounds (gaussianModel 0 ν) π T < ⊤) :
    ENNReal.ofReal (2 * BanditAlgorithm.bernoulliRelativeEntropy (1 - δ) δ / γ ^ 2 *
        gaussAlloc H ν) ≤
      expectedRounds (gaussianModel 0 ν) π T := by sorry

end FairReplay.Supplement
Source
Sah, Zhang, Lian, Testing Fairness of Evolving Software under Uncertainty, STOC 2027 submission (manuscript of 2026-11-03, sha256 e23940a0a0f5960aedaf6aba60adc41e966efc604b6379b3180b06590610d025), Theorem 10.2, eq. (18), p.12 (PDF p.14)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me