{-# 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 {
    Config -> Double
cfg_alpha      :: {-# UNPACK #-} !Double
  , Config -> Double
cfg_log_thresh :: {-# UNPACK #-} !Double  -- log (1 / alpha)
  }

-- | The trials so far, as their counts.
data State = State {
    State -> Int
st_n :: {-# UNPACK #-} !Int
  , State -> 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 :: Double -> Either ConfigError Config
config !Double
alpha
  | Bool -> Bool
not (Double -> Bool
finite Double
alpha Bool -> Bool -> Bool
&& Double
alpha Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
0 Bool -> Bool -> Bool
&& Double
alpha Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
< Double
1) =
      ConfigError -> Either ConfigError Config
forall a b. a -> Either a b
Left (Double -> ConfigError
InvalidAlpha Double
alpha)
  | Bool
otherwise = Config -> Either ConfigError Config
forall a b. b -> Either a b
Right (Double -> Double -> Config
Config Double
alpha (Double -> Double
forall a. Floating a => a -> a
log (Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
alpha)))
{-# INLINE config #-}

-- | The state before any trial.
initial :: Config -> State
initial :: Config -> State
initial Config
_ = Int -> Int -> State
State Int
0 Int
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 :: Int -> Int -> Maybe State
from_counts !Int
s !Int
n
  | Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
s = Maybe State
forall a. Maybe a
Nothing
  | Bool
otherwise = State -> Maybe State
forall a. a -> Maybe a
Just (Int -> Int -> State
State Int
n Int
s)
{-# INLINE from_counts #-}

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

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

-- | The number of successes so far.
successes :: State -> Int
successes :: State -> Int
successes = State -> Int
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 -> (Double, Double)
interval Config{Double
cfg_alpha :: Config -> Double
cfg_log_thresh :: Config -> Double
cfg_alpha :: Double
cfg_log_thresh :: Double
..} (State Int
n Int
s)
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = (Double
0, Double
1)
  | Bool
otherwise = (Double
lower, Double
upper)
  where
    !phat :: Double
phat = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
s Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n :: Double
    !ln1 :: Double
ln1 = Double -> Double
forall a. Floating a => a -> a
log (Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
1)
    inside :: Double -> Bool
inside Double
r = Double -> Double
forall a. Num a => a -> a
negate Double
ln1 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Int -> Int -> Double -> Double
log_binom Int
s Int
n Double
r Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
< Double
cfg_log_thresh
    lower :: Double
lower
      | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Double
0
      | Bool
otherwise = (Double, Double) -> Double
forall a b. (a, b) -> a
fst (Double -> Double -> (Double, Double)
bisect Double
0 Double
phat)
    upper :: Double
upper
      | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n = Double
1
      | Bool
otherwise = (Double, Double) -> Double
forall a b. (a, b) -> b
snd (Double -> Double -> (Double, Double)
bisect Double
phat Double
1)
    -- halving until the midpoint is one of the ends: the bracket as
    -- narrow as doubles allow, at any scale of rate
    bisect :: Double -> Double -> (Double, Double)
bisect Double
lo Double
hi = Double -> Double -> (Double, Double)
go Double
lo Double
hi
      where
        !side :: Bool
side = Double -> Bool
inside Double
lo
        go :: Double -> Double -> (Double, Double)
go Double
x Double
y =
          let !m :: Double
m = Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
+ (Double
y Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
x) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
2
          in  if Double
m Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
<= Double
x Bool -> Bool -> Bool
|| Double
m Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
>= Double
y then (Double
x, Double
y)
              else if Double -> Bool
inside Double
m Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== Bool
side then Double -> Double -> (Double, Double)
go Double
m Double
y else Double -> Double -> (Double, Double)
go Double
x Double
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 :: Int -> Int -> Double -> Double
log_binom Int
s Int
n Double
r
  | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Double
nN Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double -> Double
forall a. Floating a => a -> a
log1p (Double -> Double
forall a. Num a => a -> a
negate Double
r)
  | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n = Double
nN Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double -> Double
forall a. Floating a => a -> a
log Double
r
  | Bool
otherwise =
      Int -> Double
stirlerr Int
n Double -> Double -> Double
forall a. Num a => a -> a -> a
- Int -> Double
stirlerr Int
s Double -> Double -> Double
forall a. Num a => a -> a -> a
- Int -> Double
stirlerr (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
s)
        Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double -> Double -> Double
bd0 Double
sN (Double
nN Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
r) Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double -> Double -> Double
bd0 Double
fN (Double
nN Double -> Double -> Double
forall a. Num a => a -> a -> a
* (Double
1 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
r))
        Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
0.5 Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double -> Double
forall a. Floating a => a -> a
log (Double
nN Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ (Double
tau Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
sN Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
fN))
  where
    !nN :: Double
nN = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n :: Double
    !sN :: Double
sN = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
s :: Double
    !fN :: Double
fN = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
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 :: Double -> Double -> Double
bd0 !Double
x !Double
np
  | Double -> Double
forall a. Num a => a -> a
abs (Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
np) Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
< Double
0.1 Double -> Double -> Double
forall a. Num a => a -> a -> a
* (Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
np) =
      let !v :: Double
v = (Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
np) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ (Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
np)
          go :: Double -> Double -> Double -> Double
go !Double
acc !Double
ej !Double
j =
            let !ej' :: Double
ej' = Double
ej Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
v Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
v
                !acc' :: Double
acc' = Double
acc Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
ej' Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ (Double
2 Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
j Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
1)
            in  if Double
acc' Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double
acc then Double
acc' else Double -> Double -> Double -> Double
go Double
acc' Double
ej' (Double
j Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
1)
      in  Double -> Double -> Double -> Double
go ((Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
np) Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
v) (Double
2 Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
v) (Double
1 :: Double)
  | Bool
otherwise = Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double -> Double
forall a. Floating a => a -> a
log (Double
x Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
np) Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
np Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
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 :: Int -> Double
stirlerr Int
k
  | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
16 = Int -> Double
log_factorial Int
k Double -> Double -> Double
forall a. Num a => a -> a -> a
- (Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double -> Double
forall a. Floating a => a -> a
log Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
0.5 Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double -> Double
forall a. Floating a => a -> a
log (Double
tau Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
x))
  | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
500 = (Double
s0 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
s1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
x
  | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
80 = (Double
s0 Double -> Double -> Double
forall a. Num a => a -> a -> a
- (Double
s1 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
s2 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
x
  | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
35 = (Double
s0 Double -> Double -> Double
forall a. Num a => a -> a -> a
- (Double
s1 Double -> Double -> Double
forall a. Num a => a -> a -> a
- (Double
s2 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
s3 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
x
  | Bool
otherwise = (Double
s0 Double -> Double -> Double
forall a. Num a => a -> a -> a
- (Double
s1 Double -> Double -> Double
forall a. Num a => a -> a -> a
- (Double
s2 Double -> Double -> Double
forall a. Num a => a -> a -> a
- (Double
s3 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
s4 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
xx) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
x
  where
    !x :: Double
x = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k :: Double
    !xx :: Double
xx = Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
x
    s0 :: Double
s0 = Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
12
    s1 :: Double
s1 = Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
360
    s2 :: Double
s2 = Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
1260
    s3 :: Double
s3 = Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
1680
    s4 :: Double
s4 = Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
1188

-- log k!, for small k
log_factorial :: Int -> Double
log_factorial :: Int -> Double
log_factorial Int
k = (Double -> Int -> Double) -> Double -> [Int] -> Double
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' (\Double
acc Int
j -> Double
acc Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double -> Double
forall a. Floating a => a -> a
log (Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
j)) Double
0 [Int
2 .. Int
k]

tau :: Double
tau :: Double
tau = Double
2 Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
forall a. Floating a => a
pi