Eqs. (38)–(39) — the four-way differential vanishes under and equals iff under
ProvedFairReplay.eq_38_39fairness-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-testing
Let with , old thresholds at the edge , and define the pathwise differential of a four-way replay round on the tape value by
Then:
- under the null new thresholds , for every ;
- under the alternative new thresholds , for every ,
- under the alternative, for .
This is the statistic of the four-way test: a single observation is impossible under the null.
Formalization Note Outputs true/false are read as the integers /.
Differences from the source:
- encoding: outputs P_j(x;U) ∈ {0,1} and W an integer → Boolean outputs read as 0/1 in ℤ; reason: Lean convention; same values
- encoding: for every U, W = 0 almost surely, and probability d → for every U ∈ [0, 1], W = 0 (pointwise), and uniformTape-mass d of {W = 1}; reason: U ~ Unif[0, 1] takes its values in [0, 1], the support of the tape law; the pointwise identity is what the page proves ('identical for every U')
Preamble
import Mathlib import Definitions.Def_FairReplay_fourWayModel open MeasureTheory
Formal statement
namespace FairReplay
/-- **Eqs. (38)–(39), the pathwise differential of four-way replay** (Sah, Zhang, Lian, *Testing Fairness of Evolving Software under Uncertainty*, STOC 2027
submission (manuscript of 2026-11-03, sha256 e23940a0…), proof of
Theorem 10.4, eqs. (38)–(39), pp.14–15 (PDF pp.16–17)): "Under four-way replay, define the
pathwise differential W = (P1(u; U) − P0(u; U)) − (P1(v; U) − P0(v; U)). Under H0, the two endpoint
deltas are identical for every U, so W = 0 almost surely. Under H1, W = 1 ⟺ U ∈ (p + s, p + s + d],
which occurs with probability d."
With old thresholds `(p, p)`, `W(new, U)` is the differential computed from the four-way outputs
`fourWayObs ![p, p] new U = (P0(u;U), P1(u;U), P0(v;U), P1(v;U))`, outputs read as `0/1` integers.
Under the null new thresholds `(p + s, p + s)` it vanishes for every tape value `U ∈ [0, 1]`; under
the alternative `(p + s + d, p + s)` it equals `1` exactly when `U ∈ (p + s, p + s + d]`, an event of
uniform-tape probability `d`.
**Formalization Note** Outputs `true/false` are read as `1/0` in `ℤ`. The endpoint `u` is index `0`
of the threshold vectors. -/
theorem eq_38_39 (p s d : ℝ) (hp : 0 < p) (hs : 0 < s) (hd : 0 < d) (hpsd : p + s + d < 1) :
let b : Bool → ℤ := fun x => if x then 1 else 0
let W : (Fin 2 → ℝ) → ℝ → ℤ := fun new U =>
(b (fourWayObs ![p, p] new U 1) - b (fourWayObs ![p, p] new U 0)) -
(b (fourWayObs ![p, p] new U 3) - b (fourWayObs ![p, p] new U 2))
(∀ U ∈ Set.Icc (0 : ℝ) 1, W ![p + s, p + s] U = 0) ∧
(∀ U ∈ Set.Icc (0 : ℝ) 1, W ![p + s + d, p + s] U = 1 ↔ U ∈ Set.Ioc (p + s) (p + s + d)) ∧
uniformTape {U | W ![p + s + d, p + s] U = 1} = ENNReal.ofReal d := by sorry
end FairReplay
Source
Sah, Zhang, Lian, Testing Fairness of Evolving Software under Uncertainty, STOC 2027 submission (manuscript of 2026-11-03, sha256 e23940a0a0f5960aedaf6aba60adc41e966efc604b6379b3180b06590610d025), proof of Theorem 10.4, eqs. (38)–(39), pp.14–15 (PDF pp.16–17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.