, , and the truncation budget
DefinitionFairReplay_Supplement_TwoClassFamily_Bcapfairness-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-testing
With and :
and, for , with the same quantities at level ,
These are the expected stopping costs of the sequential boundary block and the Markov truncation budget of Theorem 10.9(vi)–(vii).
Formalization Note The maximum over is a real supremum over its elements, a genuine maximum when .
Definition code
import Mathlib
import Definitions.Def_FairReplay_Supplement_TwoClassFamily
import Definitions.Def_FairReplay_Supplement_TwoClassFamily_coverLP
import Definitions.Def_FairReplay_Supplement_TwoClassFamily_QLB
namespace FairReplay.Supplement
/-- The reverse boundary divergence `J_bnd(τ, d) = (τ + d) log((τ + d)/τ) + (r − d) log((r − d)/r)`,
`r = 1 − p − s − τ` (Theorem 10.9(vi), eq. (74), p.20). -/
noncomputable def Jbnd (p s τ d : ℝ) : ℝ :=
(τ + d) * Real.log ((τ + d) / τ) +
((1 - p - s - τ) - d) * Real.log (((1 - p - s - τ) - d) / (1 - p - s - τ))
/-- `H0 = (log(1/δ) + log(r/(r − d)))/K_bnd(τ, d)` (Theorem 10.9(vi), eq. (75), p.20). -/
noncomputable def H0 (p s τ d δ : ℝ) : ℝ :=
(Real.log (1 / δ) + Real.log ((1 - p - s - τ) / ((1 - p - s - τ) - d))) / Kbnd p s τ d
/-- `H1 = (log(m/δ) + log(1 + d/τ))/J_bnd(τ, d)` (Theorem 10.9(vi), eq. (75), p.20). -/
noncomputable def H1 (p s τ d δ : ℝ) (m : ℕ) : ℝ :=
(Real.log (m / δ) + Real.log (1 + d / τ)) / Jbnd p s τ d
namespace TwoClassFamily
/-- **The Markov truncation budget** `B_η` (Sah, Zhang, Lian, *Testing Fairness of Evolving Software
under Uncertainty*, STOC 2027 submission, manuscript of 2026-11-03, sha256 e23940a0…, Theorem
10.9(vii), eq. (80), p.21 (PDF p.23)):
`B_η = (δ − η)⁻¹ max_{x ∈ U} { H0(η) Σ_{z ∈ U∖{x}} c̄_z + H1(η) c̄_x }`, with `m = |U|`.
**Formalization Note** The maximum over the finite set `U` is a real `iSup` over its elements; it is
a genuine maximum when `U ≠ ∅`, the only case in which it is used. -/
noncomputable def Bcap (F : TwoClassFamily) (p s τ d δ η : ℝ) : ℝ :=
(δ - η)⁻¹ * ⨆ x : F.unmatched,
(H0 p s τ d η * ∑ z ∈ F.unmatched.erase x, F.cbar z +
H1 p s τ d η F.unmatched.card * F.cbar x)
end TwoClassFamily
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.9(vi), eqs. (74)–(75), p.20 and (vii), eq. (80), p.21 (PDF pp.22–23)