packages feed

ppad-eproc-0.5.2: lib/Numeric/Eproc/ConfSeq/Bernoulli.hs

{-# OPTIONS_HADDOCK prune #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RecordWildCards #-}

-- |
-- Module: Numeric.Eproc.ConfSeq.Bernoulli
-- Copyright: (c) 2026 Jared Tobin
-- License: MIT
-- Maintainer: Jared Tobin <jared@ppad.tech>
--
-- Anytime-valid confidence sequence for a Bernoulli rate, by
-- Robbins' method of mixtures.
--
-- For trials @x_t@ in @{0, 1}@, i.i.d. with rate @r@, after @s@
-- successes in @n@ trials, the likelihood ratio of the uniform
-- mixture over rates against @r@,
--
--     @M_n(r) = B(s + 1, n - s + 1) \/ (r^s (1 - r)^(n - s))@
--
-- (@B@ the beta function), is a nonnegative martingale under @r@
-- with @M_0(r) = 1@. By Ville's inequality it ever reaches
-- @1 \/ alpha@ with probability at most @alpha@, so the rates it has
-- not reached that against,
--
--     @C_n = { r : M_n(r) < 1 \/ alpha }@,
--
-- cover the true rate at every @n@ at once with probability at least
-- @1 - alpha@: inspect after every trial and stop when you like. As
-- @B(s + 1, n - s + 1) = 1 \/ ((n + 1) C(n, s))@,
--
--     @log M_n(r) = - log(n + 1) - log P(s; n, r)@,
--
-- @P@ the binomial probability, computed by Loader's saddle-point
-- expansion (as R's @dbinom@): stable at any count, where a
-- difference of log-factorials of size @n log n@ is not.
-- @log M_n@ is convex in @r@ and at most zero at @s \/ n@, so @C_n@
-- is an interval about @s \/ n@, its ends found by bisection; its
-- half-width is about
--
--     @sqrt(2 r (1 - r) (log(1 \/ alpha) + log(tau n r (1 - r)) \/ 2) \/ n)@
--
-- (@tau = 2 pi@), the price of anytime validity a term in @log n@.
--
-- Unlike "Numeric.Eproc.ConfSeq", which bets over a finite grid of
-- candidate means of any bounded variable, this is exact for a rate,
-- however small, and depends on the trials only through their
-- counts: 'from_counts' resumes from a tally kept elsewhere.
--
-- == Example
--
-- >>> let Right cfg = config 0.05
-- >>> let Just st = from_counts 30 100
-- >>> let (lo, hi) = interval cfg st
-- >>> lo < 0.3 && 0.3 < hi
-- True

module Numeric.Eproc.ConfSeq.Bernoulli (
  -- * Configuration and state
    Config
  , State
  , ConfigError(..)

  -- * Construction
  , config
  , initial
  , from_counts

  -- * Streaming
  , update

  -- * Inspection
  , interval
  , samples
  , successes
  ) where

import qualified Data.List as L
import Numeric (log1p)

import Numeric.Eproc.Common (ConfigError(..), finite)

-- | Confidence-sequence configuration.
data Config = Config {
    cfg_alpha      :: {-# UNPACK #-} !Double
  , cfg_log_thresh :: {-# UNPACK #-} !Double  -- log (1 / alpha)
  }

-- | The trials so far, as their counts.
data State = State {
    st_n :: {-# UNPACK #-} !Int
  , st_s :: {-# UNPACK #-} !Int
  }

-- | Build a 'Config' at a level in @(0, 1)@.
--
--   >>> either (const False) (const True) (config 0.05)
--   True
config :: Double -> Either ConfigError Config
config !alpha
  | not (finite alpha && alpha > 0 && alpha < 1) =
      Left (InvalidAlpha alpha)
  | otherwise = Right (Config alpha (log (1 / alpha)))
{-# INLINE config #-}

-- | The state before any trial.
initial :: Config -> State
initial _ = State 0 0
{-# INLINE initial #-}

-- | The state after some successes of some trials, where there are
--   no more successes than trials and neither is negative.
--
--   >>> maybe False (const True) (from_counts 3 2)
--   False
from_counts :: Int -> Int -> Maybe State
from_counts !s !n
  | s < 0 || n < s = Nothing
  | otherwise = Just (State n s)
{-# INLINE from_counts #-}

-- | The state after one more trial, a success or not.
update :: Config -> State -> Bool -> State
update _ (State n s) x = State (n + 1) (if x then s + 1 else s)
{-# INLINE update #-}

-- | The number of trials so far.
samples :: State -> Int
samples = st_n
{-# INLINE samples #-}

-- | The number of successes so far.
successes :: State -> Int
successes = st_s
{-# INLINE successes #-}

-- | The confidence interval after the trials so far, @(0, 1)@ before
--   any. Each end is the outside one of the bracket a bisection
--   leaves it in, to the precision of a double, so that the interval
--   errs wide.
--
--   >>> let Right cfg = config 0.05
--   >>> interval cfg (initial cfg)
--   (0.0,1.0)
interval :: Config -> State -> (Double, Double)
interval Config{..} (State n s)
  | n <= 0 = (0, 1)
  | otherwise = (lower, upper)
  where
    !phat = fromIntegral s / fromIntegral n :: Double
    !ln1 = log (fromIntegral n + 1)
    inside r = negate ln1 - log_binom s n r < cfg_log_thresh
    lower
      | s == 0 = 0
      | otherwise = fst (bisect 0 phat)
    upper
      | s == n = 1
      | otherwise = snd (bisect phat 1)
    -- halving until the midpoint is one of the ends: the bracket as
    -- narrow as doubles allow, at any scale of rate
    bisect lo hi = go lo hi
      where
        !side = inside lo
        go x y =
          let !m = x + (y - x) / 2
          in  if m <= x || m >= y then (x, y)
              else if inside m == side then go m y else go x m

-- log P(s; n, r), the binomial probability of s successes in n trials
-- at rate r, by Loader's saddle-point expansion: Stirling's error
-- terms, the deviances of s from n r and of n - s from n (1 - r), and
-- the normal constant
log_binom :: Int -> Int -> Double -> Double
log_binom s n r
  | s == 0 = nN * log1p (negate r)
  | s == n = nN * log r
  | otherwise =
      stirlerr n - stirlerr s - stirlerr (n - s)
        - bd0 sN (nN * r) - bd0 fN (nN * (1 - r))
        + 0.5 * log (nN / (tau * sN * fN))
  where
    !nN = fromIntegral n :: Double
    !sN = fromIntegral s :: Double
    !fN = fromIntegral (n - s) :: Double

-- the deviance x log(x / np) + np - x, by its series where x is near
-- np, where the direct form cancels
bd0 :: Double -> Double -> Double
bd0 !x !np
  | abs (x - np) < 0.1 * (x + np) =
      let !v = (x - np) / (x + np)
          go !acc !ej !j =
            let !ej' = ej * v * v
                !acc' = acc + ej' / (2 * j + 1)
            in  if acc' == acc then acc' else go acc' ej' (j + 1)
      in  go ((x - np) * v) (2 * x * v) (1 :: Double)
  | otherwise = x * log (x / np) + np - x

-- Stirling's error, log k! - (k log k - k + log(tau k) / 2), for k at
-- least one: directly below 16, by its series above
stirlerr :: Int -> Double
stirlerr k
  | k < 16 = log_factorial k - (x * log x - x + 0.5 * log (tau * x))
  | k > 500 = (s0 - s1 / xx) / x
  | k > 80 = (s0 - (s1 - s2 / xx) / xx) / x
  | k > 35 = (s0 - (s1 - (s2 - s3 / xx) / xx) / xx) / x
  | otherwise = (s0 - (s1 - (s2 - (s3 - s4 / xx) / xx) / xx) / xx) / x
  where
    !x = fromIntegral k :: Double
    !xx = x * x
    s0 = 1 / 12
    s1 = 1 / 360
    s2 = 1 / 1260
    s3 = 1 / 1680
    s4 = 1 / 1188

-- log k!, for small k
log_factorial :: Int -> Double
log_factorial k = L.foldl' (\acc j -> acc + log (fromIntegral j)) 0 [2 .. k]

tau :: Double
tau = 2 * pi