Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Composite thresholded problem and QthrQ_{\mathrm{thr}}Qthr​

Definition
FairReplay_Supplement_Qthr

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

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

The composite thresholded problem (49) asks, from four-way replay rounds, to distinguish

H0: ∣p1,u−p1,v∣≤τfromH1: ∣p1,u−p1,v∣≥τ+d,H_0:\ |p_{1,u}-p_{1,v}|\le\tau\qquad\text{from}\qquad H_1:\ |p_{1,u}-p_{1,v}|\ge\tau+d,H0​: ∣p1,u​−p1,v​∣≤τfromH1​: ∣p1,u​−p1,v​∣≥τ+d,

uniformly over all old and new thresholds in [0,1][0,1][0,1]. A tester is correct at level δ\deltaδ if it rejects with probability at most δ\deltaδ under every instance of H0H_0H0​ and fails to reject with probability at most δ\deltaδ under every instance of H1H_1H1​.

In the P18 family (old thresholds (p,p)(p,p)(p,p), boundary-null new thresholds (p+s+τ,p+s)(p+s+\tau,p+s)(p+s+τ,p+s), alternative (p+s+τ+d,p+s)(p+s+\tau+d,p+s)(p+s+τ+d,p+s)), two optimal null expected round counts are defined:

  1. QthrpairQ_{\mathrm{thr}}^{\mathrm{pair}}Qthrpair​, over testers that are δ\deltaδ-correct for the boundary null against the alternative;
  2. QthrcompQ_{\mathrm{thr}}^{\mathrm{comp}}Qthrcomp​, over testers correct for the whole composite problem, with the expectation under the boundary null.

Formalization Note The paper writes Qthr(τ,d,δ)Q_{\mathrm{thr}}(\tau,d,\delta)Qthr​(τ,d,δ) without a displayed definition; both readings are bounded in Theorem 10.5. Infima are in [0,∞][0,\infty][0,∞]; non-stopping counts as an error under H1H_1H1​.

Definition code
import Mathlib
import Definitions.Def_BanditTrajectory
import Definitions.Def_FairReplay_IsDeltaCorrect
import Definitions.Def_FairReplay_expectedRounds
import Definitions.Def_FairReplay_optRounds
import Definitions.Def_FairReplay_Supplement_fourWayEnv

open MeasureTheory

namespace FairReplay.Supplement

/-- **Correctness for the composite thresholded problem** (Sah, Zhang, Lian, *Testing Fairness of
Evolving Software under Uncertainty*, STOC 2027 submission, manuscript of 2026-11-03,
sha256 e23940a0…, Theorem 10.5, eq. (49), p.16 (PDF p.18)):
`H0 : |p1,u − p1,v| ≤ τ, H1 : |p1,u − p1,v| ≥ τ + d`.

A four-way tester `(π, T, ψ)` is correct at level `δ` for this problem if, for all old thresholds and
new thresholds in `[0, 1]`, it stops and rejects with probability at most `δ` whenever the new
endpoint gap is at most `τ`, and fails to stop-and-reject with probability at most `δ` whenever the
gap is at least `τ + d`.

**Formalization Note** The stopping time is named `T` (the paper's `τ` is the tolerance here). A run
that never stops counts as an error under `H1`. -/
def IsThrCompositeCorrect (τ d δ : ℝ) (π : BanditAlgorithm.BanditPolicy 1)
    (T : (ℕ → Fin 1 × ℝ) → ℕ∞) (ψ : (ℕ → Fin 1 × ℝ) → Bool) : Prop :=
  (∀ old new : Fin 2 → ℝ, (∀ j, old j ∈ Set.Icc (0 : ℝ) 1) → (∀ j, new j ∈ Set.Icc (0 : ℝ) 1) →
      |new 0 - new 1| ≤ τ →
      BanditAlgorithm.banditTrajMeasure (fourWayEnv old new) π {ω | T ω < ⊤ ∧ ψ ω = true} ≤
        ENNReal.ofReal δ) ∧
  (∀ old new : Fin 2 → ℝ, (∀ j, old j ∈ Set.Icc (0 : ℝ) 1) → (∀ j, new j ∈ Set.Icc (0 : ℝ) 1) →
      τ + d ≤ |new 0 - new 1| →
      BanditAlgorithm.banditTrajMeasure (fourWayEnv old new) π {ω | ¬ (T ω < ⊤ ∧ ψ ω = true)} ≤
        ENNReal.ofReal δ)

/-- **`Q_thr` for the boundary pair** (Theorem 10.5, eq. (51), p.16): the optimal null expected
number of four-way rounds over testers that are δ-correct for the P18 boundary null (old `(p, p)`,
new `(p + s + τ, p + s)`) against the alternative (new `(p + s + τ + d, p + s)`).

**Formalization Note** The paper gives no displayed definition of `Q_thr`; this and `QthrComp`
are the two natural readings, and Theorem 10.5's `Θ` statement bounds both. -/
noncomputable def QthrPair (p s τ d δ : ℝ) : ENNReal :=
  optRounds δ (fourWayEnv ![p, p] ![p + s + τ, p + s]) (fourWayEnv ![p, p] ![p + s + τ + d, p + s])

/-- **`Q_thr` for the composite problem** (Theorem 10.5, eqs. (49), (51), p.16): the infimum of the
expected number of rounds under the P18 boundary null over all four-way testers that are correct at
level `δ` for the whole composite problem (49). The infimum is in `[0, ∞]`. -/
noncomputable def QthrComp (p s τ d δ : ℝ) : ENNReal :=
  ⨅ (π : BanditAlgorithm.BanditPolicy 1) (T : (ℕ → Fin 1 × ℝ) → ℕ∞)
    (ψ : (ℕ → Fin 1 × ℝ) → Bool) (hT : BanditAlgorithm.IsBanditStoppingTime T)
    (_ : Measurable[hT.measurableSpace] ψ) (_ : IsThrCompositeCorrect τ d δ π T ψ),
    expectedRounds (fourWayEnv ![p, p] ![p + s + τ, p + s]) π T

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.5, eqs. (49), (51), p.16 (PDF p.18)

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