Composite thresholded problem and
DefinitionFairReplay_Supplement_Qthrfairness-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-testing
The composite thresholded problem (49) asks, from four-way replay rounds, to distinguish
uniformly over all old and new thresholds in . A tester is correct at level if it rejects with probability at most under every instance of and fails to reject with probability at most under every instance of .
In the P18 family (old thresholds , boundary-null new thresholds , alternative ), two optimal null expected round counts are defined:
- , over testers that are -correct for the boundary null against the alternative;
- , over testers correct for the whole composite problem, with the expectation under the boundary null.
Formalization Note The paper writes without a displayed definition; both readings are bounded in Theorem 10.5. Infima are in ; non-stopping counts as an error under .
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)