| Copyright | (c) 2026 Jared Tobin |
|---|---|
| License | MIT |
| Maintainer | Jared Tobin <jared@ppad.tech> |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Numeric.Eproc.ConfSeq
Description
Anytime-valid confidence sequence for the mean of bounded observations.
For samples x_t in [lo, hi] with common conditional mean
mu = E[x_t | F_{t-1}] for all t(F_{t-1} being the filtration generated by everything observed
strictly before time t; for i.i.d. samples this is just
E[x]), the running state yields a confidence interval C_t
after every observation, with time-uniform coverage:
P(for all t, mu in C_t) >= 1 - alpha
whenever C_t is reported at all (see interval for the empty
case). The guarantee holds uniformly over time, so the user may
inspect the interval after every observation and stop at any
data-dependent time -- optional stopping does not erode coverage.
The construction is the hedged capital confidence sequence of
Waudby-Smith & Ramdas (2024), Theorem 3, evaluated over a finite
grid of candidate means. All arithmetic is carried out in
[0, 1] coordinates internally; observations are mapped affinely
at the boundary. Each candidate m runs a pair of betting
processes: a positive-direction capital K^+_t(m) wagering
that the mean exceeds m, and a negative-direction capital
K^-_t(m) wagering the reverse. The base bet is a single
predictable plug-in (their eq. (26)), computed once per update
from the running regularized mean and variance of the data and
shared by every candidate: it never depends on m, and only a
final truncation to c / m (respectively c / (1 - m)), with
c = 1/2, is candidate-specific. This m-freeness is what
makes the survivor set provably an interval (Theorem 3);
m-dependent bets can produce non-interval survivor sets (their
Section E.4), which is why this module does not use the library's
Bettor strategies.
A candidate m is rejected once the max-hedge (theta = 1/2)
capital max(K^+_t(m), K^-_t(m)) / 2 crosses 1 / alpha.
Under the truth m = mu each capital process is a nonnegative
supermartingale, the max is dominated by the convex combination
(K^+ + K^-) / 2, and Ville's inequality bounds the probability
that the truth is ever rejected by alpha. No multiplicity
correction across grid candidates is needed: coverage concerns
only the true mean's own test, and rejection of other candidates
merely tightens the interval.
Grid resolution is an accuracy/cost knob. Interval endpoints are
quantized to the grid -- a g-point grid resolves them to within
(hi - lo) / (g + 1) -- and per-update cost is O(live
candidates), shrinking as evidence accumulates and candidates
are rejected.
Example
Estimate the mean of a stream in [0, 1] with empirical mean
0.8, at level alpha = 0.05 on a 100-point grid:
>>>let Right cfg = config 0.0 1.0 0.05 100>>>let xs = concat (replicate 50 [1, 1, 0, 1, 1, 0, 1, 1, 1, 1])>>>interval cfg (foldl' (update cfg) (initial cfg) xs)Just (0.7326732673267327,0.8613861386138614)
Confidence-sequence configuration and state
Confidence-sequence configuration. Build with config.
Carries the sample bounds, the significance level, the grid
size, and the precomputed per-candidate rejection threshold
log(2 / alpha) along with the bet numerator
2 log(2 / alpha).
Streaming confidence-sequence state. Construct with initial
and fold observations through update.
Carries the sample count, the shared plug-in bettor statistics
(regularized running sums in [0, 1] coordinates), and the
live grid candidates. Rejected candidates are dropped
permanently, so the reported intervals are nested.
Invariant: initial and update construct the live list fully
forced -- no thunks in the spine or the elements -- so a State
in WHNF is already in normal form.
data ConfigError Source #
Reasons that a test-configuration smart constructor can reject
its inputs. Returned by config,
configInterval,
config,
config,
config, and
config.
Constructors
| InvalidAlpha !Double | significance level outside |
| InvalidBounds !Double !Double | sample bounds violate |
| InvalidNullMean !Double !Double !Double | null mean outside |
| InvalidNullInterval !Double !Double !Double !Double | null-interval endpoints violate |
| InvalidBaselineRate !Double | baseline rate outside |
| InvalidComponentCount !Int | component count not positive |
| InvalidGridSize !Int | grid size below |
Instances
| Show ConfigError Source # | |
Defined in Numeric.Eproc.Common Methods showsPrec :: Int -> ConfigError -> ShowS # show :: ConfigError -> String # showList :: [ConfigError] -> ShowS # | |
| Eq ConfigError Source # | |
Defined in Numeric.Eproc.Common | |
Construction
Arguments
| :: Double | sample lower bound |
| -> Double | sample upper bound |
| -> Double | significance level |
| -> Int | grid size |
| -> Either ConfigError Config |
Build a Config for the confidence sequence.
The candidate means form the interior grid
m_j = lo + (j / (g + 1)) * (hi - lo), j = 1 .. g
(endpoints excluded, so that in [0, 1] coordinates the bet
truncations c / m and c / (1 - m) stay finite). The
per-candidate rejection threshold log(2 / alpha) and the bet
numerator 2 log(2 / alpha) are precomputed.
Returns Left with a ConfigError on inputs that would leave
the mathematical regime: alpha non-finite or outside
(0, 1); lo or hi non-finite, or lo >= hi; or a grid
size below 1.
>>>let Right cfg = config 0.0 1.0 0.05 100
initial :: Config -> State Source #
The initial State for a fresh confidence sequence.
Every grid candidate starts live with both log-capitals at 0
(i.e., K^+ = K^- = 1); the shared bettor statistics start
from their regularized priors (mu_0 = 1/2,
sigma^2_0 = 1/4 in [0, 1] coordinates).
>>>let s0 = initial cfg
Streaming
update :: Config -> State -> Double -> State Source #
Fold one observation into the running State.
Maps the observation to [0, 1] coordinates via
y = (x - lo) / (hi - lo) and computes the shared predictable
plug-in bet from the statistics accumulated through the
previous step (Waudby-Smith & Ramdas (2024), eq. (26)):
lambda_t = sqrt (2 log(2 / alpha)
/ (sigma^2_{t-1} * t * log(1 + t)))The bet is computed once and shared across all
live candidates -- its independence from m is what keeps the
survivor set an interval. Each live candidate m then updates
its pair of log-capitals with the truncated bets
min lambda_t (c / m) and min lambda_t (c / (1 - m)),
with c = 1/2, and
is dropped iff max(log K^+, log K^-) has reached
log(2 / alpha). Finally y is folded into the shared
statistics, preserving predictability of the next bet.
Precondition: x must lie in the [lo, hi] interval given
to config. The coverage guarantee of the sequence depends on
it. Out-of-range observations can drive a capital factor
negative, taking the construction out of the supermartingale
regime entirely; the function does not check for this.
>>>let s1 = update cfg s0 0.7
Inspection
interval :: Config -> State -> Maybe (Double, Double) Source #
The current confidence interval, in the original [lo, hi]
coordinates.
The interval spans the surviving grid candidates, widened by
one grid step at each end (or clamped to lo / hi at the
grid's edges). The widening is what makes off-grid true means
safe: Theorem 3 guarantees the ideal continuum survivor set is
an interval, so its endpoints are bracketed by the nearest
rejected grid candidates, and reporting those sentinels
yields a superset of the continuum interval. Whenever the
result is Just, it therefore covers the true mean uniformly
over time with probability at least 1 - alpha -- no
multiplicity correction across candidates is needed, since
coverage concerns only the true mean's own test.
Nothing means every grid candidate has been rejected: the
evidence has resolved the mean below the grid's resolution.
For a true mean lying exactly on the grid this has probability
at most alpha (its own test must have rejected). For an
off-grid true mean it additionally occurs once the continuum
survivor interval shrinks inside a single grid cell -- a
quantization horizon far beyond the point where the reported
width is comparable to the grid spacing. Treat Nothing as a
signal to rerun with a larger grid, not as an inference.
>>>interval cfg (initial cfg)Just (0.0,1.0)