Struct BernoulliConfidenceSequence 

pub struct BernoulliConfidenceSequence { /* private fields */ }

Anytime-valid confidence sequence for a Bernoulli proportion: Robbins’ beta-binomial mixture with a uniform Beta(1, 1) prior.

Why not just re-run wilson_interval

A fixed-n interval is only valid if n was fixed before the data. An adaptive driver that watches the interval after every trial and stops when it looks tight enough is doing optional stopping, and a fixed-n interval checked that way has no coverage guarantee at all: the error rate grows with the number of peeks. A confidence sequence is instead a whole family of intervals, one per n, that are simultaneously valid:

P( there exists n >= 1 with p_true outside CS_n )  <=  alpha

so the caller may look as often as it likes, stop on any rule it likes – including a data-dependent one – and the interval it stops on still covers at the advertised rate. The price is width: at every n this interval is strictly wider than the Wilson interval on the same counts (pinned by this module’s tests). Paying it is the point.

The mixture martingale

Robbins (1970), “Statistical methods related to the law of the iterated logarithm”; the modern treatment is Howard, Ramdas, McAuliffe & Sekhon (2021), “Time-uniform, nonasymptotic, nonparametric confidence sequences”. Against a candidate value p, with S successes in n trials, mix the likelihood ratio over a uniform Beta(1, 1) prior on the alternative:

M_n(p) = integral_0^1 q^S (1-q)^(n-S) dq / [ p^S (1-p)^(n-S) ]
       = B(S+1, n-S+1) / [ p^S (1-p)^(n-S) ]

The prior’s own normaliser 1 / B(1, 1) is 1 (ln B(1,1) == 0), so it drops out. In logs, via crate::special::ln_beta:

ln M_n(p) = ln B(S+1, n-S+1) - S*ln(p) - (n-S)*ln(1-p)

When p is the true success probability, M_n is a nonnegative martingale with M_0 = 1, so Ville’s inequality bounds it uniformly over all time: P(exists n : M_n >= 1/alpha) <= alpha. Inverting that test – keeping every p the data has not yet ruled out – gives the confidence set

CS_n = { p in (0, 1) : ln M_n(p) <= ln(1/alpha) }

whose miss probability, over the whole infinite sequence at once, is at most alpha.

Asymptotics

Substituting Stirling into ln B(S+1, n-S+1) = -ln[(n+1) * C(n, S)] gives ln M_n(p) ~ n*KL(p_hat || p) - ln(n+1) + 0.5*ln(2*pi*n*p_hat*(1-p_hat)), so the half-width shrinks like sqrt((ln(1/alpha) + 0.5*ln n) * p_hat*(1-p_hat) * 2 / n) – the familiar sqrt(log(n)/n) rate of a confidence sequence, a sqrt(log n) factor wider than the sqrt(1/n) of a fixed-n interval. That extra factor is the optional-stopping licence.

Implementations

impl BernoulliConfidenceSequence

pub fn new(level: ConfidenceLevel) -> Self

A fresh sequence with no observations, at the given confidence level.

pub fn update(&mut self, hit: bool)

Folds in one more trial.

pub fn update_batch(&mut self, hits: u64, trials: u64)

Folds in trials more trials of which hits succeeded.

hits above trials saturates at trials rather than panicking or asserting, matching wilson_interval’s posture for the same malformed input so the two functions cannot disagree about what a bad count means. That choice is load-bearing here rather than merely tidy: S > n would make the second argument of ln B(S+1, n-S+1) non-positive, crate::special::ln_gamma returns NaN out of domain, and NaN > threshold is false – so bisect_endpoint would take its else arm 200 times running and return a perfectly plausible-looking number pinned to the bracket end instead of signalling anything. Saturating at the input removes that silent-wrong-answer path entirely. A debug_assert! was considered and rejected for the reason recorded on wilson_interval: it would panic under plain cargo test, leaving the documented behaviour unpinnable by an ordinary test.

Both counters saturate at u64::MAX too, which preserves the successes <= trials invariant (min(S+h, MAX) <= min(n+t, MAX) whenever S <= n and h <= t).

pub fn successes(&self) -> u64

Successes observed so far.

pub fn trials(&self) -> u64

Trials observed so far.

pub fn bounds(&self) -> (f64, f64)

The current interval: every p not yet ruled out at level alpha.

(0.0, 1.0) when no trials have been folded in – total ignorance, the same answer wilson_interval gives at n == 0, and not an error.

How the endpoints are found

d^2/dp^2 ln M_n(p) = S/p^2 + (n-S)/(1-p)^2 > 0, so ln M_n is strictly convex on (0, 1) with its unique minimum at the MLE p_hat = S/n. The confidence set is therefore a genuine interval, bounded by the two solutions of ln M_n(p) = ln(1/alpha), one on each side of p_hat.

p_hat is always strictly inside the set, so both brackets are always valid: the minimum value is ln M_n(p_hat) = -ln[(n+1) * C(n,S) * p_hat^S * (1-p_hat)^(n-S)], and the method-of-types bound (Cover & Thomas, Elements of Information Theory, Thm 11.1.4: a type’s probability under its own maximum-likelihood distribution is at least 1/(n+1)^(|alphabet|-1), here 1/(n+1)) makes that bracketed product at least 1, hence ln M_n(p_hat) <= 0 < ln(1/alpha) for every n >= 1 and every level.

Each endpoint is then bisected with exactly BISECTION_ITERS (200) steps – a fixed count, not a tolerance test. Every step halves the bracket, so after 200 the bracket is 2^-200 ~ 6e-61 of a starting width below 1.0: the loop has been sitting on two adjacent doubles since roughly step 55, and the remaining steps are no-ops that keep bounds() a pure function of (S, n, alpha) with no data-dependent trip count. Since the search resolves p to the last bit, accuracy is set by ln M_n itself, i.e. by crate::special::ln_beta: its measured ~7e-16 relative error at n = 1e6 is an absolute ~5e-10 on an ln B of magnitude ~7e5, and dividing by the slope of ln M_n at the endpoint (~9e3 there) puts the endpoint error near 1e-13 – ten orders of magnitude below the ~2e-3 half-width at that n.

Saturation

Each side saturates for either of two independent reasons.

Rule 1, the p_hat rule. The lower root can never sit above p_hat, so p_hat <= BRACKET_EPS (which includes S == 0, where p_hat is exactly 0) means the root is below anything the bracket can resolve: the bound is reported as exactly 0.0. The upper side mirrors it at p_hat >= 1 - BRACKET_EPS (including S == n, reported as exactly 1.0). This rule is what handles every small-n case, on both sides.

Rule 2, the endpoint-value guard. Independently, ln M_n evaluated at the bracket end can already sit at or below the threshold, meaning no root exists inside the bracket at all; the bound then saturates rather than bisecting for something that is not there. Despite the “tiny n” intuition this guard is not load-bearing at small n – at S = 1, n = 1 and 95% confidence, ln M_n(eps) = 33.85 against a threshold of 2.996, 30 nats away from firing, and the low bound there is a genuine root at 0.025. Every small-n case that does satisfy this guard is already caught by rule 1. It first becomes non-redundant in the opposite regime – large n with an extreme p_hat, where the true root falls below BRACKET_EPS while p_hat itself does not. Measured first firings: S = 1 at n ~ 1e7 (giving (0.0, 2.22e-6)), and S = 2 at n ~ 1e10. Do not read it as dead code because a small-n probe never reaches it.

Both saturations widen the interval, so neither can cost coverage.

pub fn half_width(&self) -> f64

Half the width of the current interval; 0.5 before any trials.

Trait Implementations

impl Clone for BernoulliConfidenceSequence

fn clone(&self) -> BernoulliConfidenceSequence

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BernoulliConfidenceSequence

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.