Sequential probability ratio test

Deep dive

How it works

Parts:

• hypotheses — two point models f0, f1 (e.g. p0 = 0.5, p1 = 0.6), the "indifference zone" is everything between them
• LLR increment — z(x) = ln f1(x)/f0(x); Bernoulli: ln(p1/p0) on success, ln((1-p1)/(1-p0)) on failure; normal mean with known sigma: (m1-m0)(x-(m0+m1)/2)/sigma^2
• accumulator — S_n = z(x_1) + … + z(x_n)
• walls — ln A = ln((1-b)/a) and ln B = ln(b/(1-a)) from the target type-I error a and type-II error b
• truncation — optional n_max; at the cap decide by the side of the midpoint

Steps:

1. Choose H0, H1, a and b before looking at data.
2. Set S = 0, n = 0.
3. For each observation: S += z(x), n += 1.
4. If S >= ln A stop and accept H1; if S <= ln B stop and accept H0.
5. If n == n_max stop and accept H1 when S is above the midpoint of the walls, else H0.
6. Otherwise take the next observation.

 S
 ln A ─────────────────────────  accept H1
         ╱╲    ╱╲╱
 0  ────╱──╲──╱────
       ╱    ╲╱                    continue
 ln B ─────────────────────────  accept H0
       n →   (drift up under H1, down under H0)

Wald's walls are bounds: actual errors satisfy a' <= a/(1-b), b' <= b/(1-a) and a' + b' <= a + b (Wald 1945, from memory). Overshoot makes real errors a little smaller than nominal (0.045 against 0.05 below).

Optimality. Among all tests, sequential or not, whose error probabilities do not exceed a and b for two simple hypotheses and i.i.d. observations, the SPRT has the smallest expected sample size under H0 and under H1 simultaneously (Wald and Wolfowitz 1948). It does not cover composite hypotheses: for a true parameter between the two points the average can exceed the fixed-n size.

Expected sample size (Wald's approximation, ignoring overshoot): E1[N] ≈ ((1-b) ln A + b ln B) / E1[z] and E0[N] ≈ (a ln A + (1-a) ln B) / E0[z]. Our run gives 131.6 and 129.8 against 137.3 and 134.9 simulated.

Game-pair variant. Engine regression tests (Fishtest, OpenBench) test an Elo gain of at least elo1 against at most elo0. Fishtest's sprt class defaults to alpha = beta = 0.05, elo0 = 0, elo1 = 5 and uses Wald's walls. Outcomes are counted as trinomial (L, D, W) or pentanomial (pair scores LL, LD, LW+DD, DW, WW). The LLR is the generalized approximation N (s1-s0)(2*s_mean - s0 - s1) / (2 var) with s = logistic score of the Elo bound and s_mean, var the empirical mean and variance of the pair score; OpenBench's code is taken from Fishtest (its header says so).

Versus peeking. Looking at a fixed-n p-value after every batch and stopping at the first p < 0.05 makes the nominal 5 % error unreliable (Johari et al.). The SPRT is built for continuous monitoring, but only for its two point hypotheses. For an unknown effect, mSPRT mixes the likelihood ratio over a prior on the effect and reports an always-valid p-value p_n = min(p_{n-1}, 1/Lambda_n) (mixture detail from memory). Group-sequential designs such as O'Brien–Fleming test at a few pre-planned looks with strict early boundaries and a final threshold near the fixed-n one (from memory).

Code

#[derive(Clone, Copy, Debug, PartialEq)]
pub enum Decision { Continue, AcceptH0, AcceptH1 }

/// Wald SPRT over a per-observation LLR closure ln f1(x)/f0(x).
pub struct Sprt<F: Fn(f64) -> f64> {
    llr_of: F, pub llr: f64, pub n: u64,
    lo: f64, hi: f64, n_max: u64, pub truncated: bool,
}
impl<F: Fn(f64) -> f64> Sprt<F> {
    pub fn new(llr_of: F, alpha: f64, beta: f64, n_max: u64) -> Self {
        Sprt { llr_of, llr: 0.0, n: 0, n_max, truncated: false,
               lo: (beta / (1.0 - alpha)).ln(), hi: ((1.0 - beta) / alpha).ln() }
    }
    pub fn update(&mut self, x: f64) -> Decision {
        self.llr += (self.llr_of)(x);
        self.n += 1;
        if self.llr >= self.hi { return Decision::AcceptH1; }
        if self.llr <= self.lo { return Decision::AcceptH0; }
        if self.n >= self.n_max {
            self.truncated = true; // decide by the nearer wall
            return if self.llr > 0.5 * (self.lo + self.hi) { Decision::AcceptH1 } else { Decision::AcceptH0 };
        }
        Decision::Continue
    }
}
/// Bernoulli, x = 1.0 or 0.0.
pub fn bernoulli_llr(p0: f64, p1: f64) -> impl Fn(f64) -> f64 {
    let (s, f) = ((p1 / p0).ln(), ((1.0 - p1) / (1.0 - p0)).ln());
    move |x| if x > 0.5 { s } else { f }
}
pub struct XorShift(pub u64);
impl XorShift {
    pub fn next_f64(&mut self) -> f64 {
        self.0 ^= self.0 << 13; self.0 ^= self.0 >> 7; self.0 ^= self.0 << 17;
        (self.0 >> 11) as f64 / (1u64 << 53) as f64
    }
}
fn run(p: f64, rng: &mut XorShift) -> (Decision, u64) {
    let mut t = Sprt::new(bernoulli_llr(0.5, 0.6), 0.05, 0.05, u64::MAX);
    loop {
        let d = t.update(if rng.next_f64() < p { 1.0 } else { 0.0 });
        if d != Decision::Continue { return (d, t.n); }
    }
}
fn main() {
    let (mut rng, runs) = (XorShift(0x9E3779B97F4A7C15), 20_000u32);
    let (mut fa, mut fb, mut n0, mut n1) = (0u32, 0u32, 0u64, 0u64);
    for _ in 0..runs {
        let (d, n) = run(0.5, &mut rng); fa += (d == Decision::AcceptH1) as u32; n0 += n;
        let (d, n) = run(0.6, &mut rng); fb += (d == Decision::AcceptH0) as u32; n1 += n;
    }
    let r = runs as f64;
    let (a, b, asn0, asn1) = (fa as f64 / r, fb as f64 / r, n0 as f64 / r, n1 as f64 / r);
    // fixed-n one-sided test, same alpha and beta (normal approximation)
    let z = 1.6448536269514722f64;
    let fixed = ((z * 0.25f64.sqrt() + z * 0.24f64.sqrt()) / 0.1).powi(2).ceil();
    assert!((0.02..0.055).contains(&a) && (0.02..0.055).contains(&b));
    assert!(asn0 < fixed && asn1 < fixed);
    println!("type-I {a:.4} type-II {b:.4} ASN {asn0:.1}/{asn1:.1} fixed {fixed}");
}

Run (release): type-I 0.0452, type-II 0.0450, average sample number 134.9 (H0) and 137.3 (H1), fixed-n 266.

Complexity and constants

Per observation: one LLR evaluation, one add, two compares; 16 bytes of state. Measured: 2.07 ns per update (Bernoulli closure, release build, Apple-silicon Mac, 200 M updates). The cost that matters is the observations: the expected count scales with ln(1/a) over the Kullback-Leibler divergence between f1 and f0, so halving a small effect roughly quadruples it.

Efficiency

• Cost: about 2 ns and 16 bytes per observation (measured); the real cost is the sampled units, which the SPRT cuts.
• Levers:
  • early stopping — ASN 135 vs fixed n 266 at 0.5 vs 0.6, a=b=0.05 (measured) — both hypotheses are point values.
  • choose H1 as the smallest effect worth shipping — sample size grows with 1/KL, so a too-small delta wastes data — design time.
  • pair outcomes (pentanomial counts) — model the correlation inside a pair (Fishtest/OpenBench input) — correlated pairs such as shared openings or shared users.
  • truncate at n_max — bounds worst-case cost; at n_max = 150 the measured errors rose to about 0.11 — when a budget is a hard limit.
• Naive → standard → state of the art:
  • fixed-n test, peeking · error guarantee void
  • fixed-n test sized by power · 266 observations in the example
  • SPRT with Wald walls and truncation · ASN about 135, bounded by n_max

Implementation notes

• Keep S in f64; clamp or reset if you run it without walls (the timing loop above does).
• Truncation raises errors: at n_max = 150 (32 % of runs hit the cap) type-I was 0.113 and type-II 0.107. Pick n_max well above the wanted ASN and check the errors by simulation.
• A swapped f0/f1 silently inverts the test: assert that z is positive where H1 is likelier.

Pitfalls

• Using nominal a and b as exact: Wald's walls are conservative (real errors below nominal), so the test can use more data than needed.
• Changing H1 mid-test or restarting after a near miss voids the error rates.
• True effect between the two points: the average sample size can exceed the fixed-n size.
• Feeding clustered data (several events per user) instead of independent units.

Variants and alternatives

In production

• Fishtest and OpenBench gate Stockfish-style engine patches with SPRT on game-pair counts.
• Sequential port-scan detection (threshold random walk) flags a host from successive connection successes and failures (Jung et al. 2004).
• A commercial online-experiment platform runs always-valid inference (Johari et al.).
• Lot acceptance and clinical-trial monitoring, the original uses of sequential tests (Wald 1945).

Implementations

Sources

• A. Wald, Sequential Tests of Statistical Hypotheses, Annals of Mathematical Statistics 16(2), 117-186, 1945. paper
• A. Wald, J. Wolfowitz, Optimum Character of the Sequential Probability Ratio Test, Annals of Mathematical Statistics 19(3), 326-339, 1948. paper
• R. Johari, L. Pekelis, D. J. Walsh, Always Valid Inference: Bringing Sequential Analysis to A/B Testing, arXiv 2015. paper
• P. C. O'Brien, T. R. Fleming, A Multiple Testing Procedure for Clinical Trials, Biometrics 35(3), 549-556, 1979. paper
• J. Jung, V. Paxson, A. Berger, H. Balakrishnan, Fast Portscan Detection Using Sequential Hypothesis Testing, IEEE Symposium on Security and Privacy, 2004.
• Fishtest server/fishtest/stats/sprt.py and LLRcalc.py. code
• OpenBench OpenBench/stats.py. code