README.md (5169B)
1 # ppad-eproc 2 3 [](https://hackage.haskell.org/package/ppad-eproc) 4  5 [](https://docs.ppad.tech/eproc) 6 7 Anytime-valid sequential hypothesis testing and confidence sequences 8 for bounded random variables, via the e-process / betting framework 9 of [Waudby-Smith & Ramdas (2024)][wsr24]. 10 11 ## Usage 12 13 A sample GHCi session: 14 15 ``` 16 > import qualified Numeric.Eproc.Bounded as Bounded 17 > 18 > -- hypothesis: E[X] = 0.5 for samples in [0, 1] at alpha = 1e-3, tested 19 > -- with the Newton bettor. 'config' returns 'Either ConfigError Config' 20 > -- and refuses inputs outside the mathematical regime. 21 > let Right cfg = Bounded.config 0.5 0.0 1.0 1.0e-3 Bounded.Newton 22 > let s0 = Bounded.initial cfg 23 > 24 > -- ten observations (drifting from hypothesis), and state afterwards 25 > let xs = [1, 1, 0, 1, 1, 0, 1, 1, 1, 1] 26 > let s10 = foldl' (Bounded.update cfg) s0 xs 27 > 28 > -- inspect current and supremum-so-far log-wealth, and the stopping 29 > -- decision, at any point 30 > Bounded.log_wealth s10 31 0.6187772969384595 32 > Bounded.log_wealth_sup s10 33 0.916290731874155 34 > Bounded.decide cfg s10 35 Continue 36 > 37 > -- with enough evidence, the hypothesis is rejected 38 > let s300 = foldl' (Bounded.update cfg) s0 (concat (replicate 30 xs)) 39 > Bounded.log_wealth_sup s300 40 51.14271142862292 41 > Bounded.decide cfg s300 42 Reject 43 ``` 44 45 Confidence sequences invert the same machinery into time-uniform 46 interval estimates: valid at every sample size simultaneously, so you 47 can watch the interval shrink and stop whenever it's tight enough: 48 49 ``` 50 > import qualified Numeric.Eproc.ConfSeq as CS 51 > 52 > -- estimate a mean in [0, 1] at 95% coverage, on a 100-point grid 53 > let Right cfg = CS.config 0.0 1.0 0.05 100 54 > let s0 = CS.initial cfg 55 > 56 > -- the same drifting stream as above; the interval closes in on 57 > -- its empirical mean of 0.8 58 > let xs = concat (replicate 30 [1, 1, 0, 1, 1, 0, 1, 1, 1, 1]) 59 > CS.interval cfg (foldl' (CS.update cfg) s0 xs) 60 Just (0.7227722772277227,0.8712871287128713) 61 ``` 62 63 Every test module also reports its evidence as an anytime-valid 64 p-value (`p_value`) and a normalized log e-value (`log_evalue`); the 65 `Mixture` module combines several e-processes into a single test with 66 power against a union of alternatives (see its haddocks for a worked 67 sign-plus-magnitude example). 68 69 ## Documentation 70 71 Haddocks (API documentation, etc.) are hosted at 72 [docs.ppad.tech/eproc](https://docs.ppad.tech/eproc). 73 74 ## Performance 75 76 The aim is best-in-class performance for pure, highly-auditable Haskell 77 code. 78 79 Current benchmark figures on an M4 Silicon MacBook Air look like (use 80 `cabal bench` to run the benchmark suite): 81 82 ``` 83 benchmarking Bounded.update (one step)/newton 84 time 13.96 ns (13.88 ns .. 14.04 ns) 85 86 benchmarking Bounded.update (1000-sample fold)/fixed 87 time 7.951 μs (7.944 μs .. 7.959 μs) 88 89 benchmarking Bounded.update (1000-sample fold)/adaptive 90 time 12.69 μs (12.68 μs .. 12.71 μs) 91 92 benchmarking Bounded.update (1000-sample fold)/newton 93 time 14.61 μs (14.57 μs .. 14.64 μs) 94 95 benchmarking Bernoulli.update (1000-sample fold)/newton 96 time 14.64 μs (14.63 μs .. 14.65 μs) 97 98 benchmarking Bernoulli.TwoSided.update (1000-sample fold)/newton 99 time 14.83 μs (14.81 μs .. 14.84 μs) 100 101 benchmarking Mixture.update (one step)/K=4 102 time 31.38 ns (31.21 ns .. 31.55 ns) 103 104 benchmarking ConfSeq.update (one step, g = 200)/plug-in 105 time 2.121 μs (2.118 μs .. 2.124 μs) 106 107 benchmarking ConfSeq.update (1000-sample fold, g = 200)/plug-in 108 time 241.2 μs (239.7 μs .. 243.2 μs) 109 ``` 110 111 The `Paired` and `Bernoulli.TwoSided` modules are thin newtype 112 wrappers over `Bounded`, and inline through with no measurable 113 overhead. `ConfSeq` updates cost O(live grid candidates) per 114 observation, so long streams get cheaper as candidates are rejected 115 (visible in the sub-linear fold figure above). See the criterion 116 suite for the full breakdown across `Fixed` / `Adaptive` / `Newton` 117 bettors and per-step / fold workloads. 118 119 You should compile with the `llvm` flag for maximum performance. 120 121 ## Development 122 123 You'll require [Nix][nixos] with [flake][flake] support enabled. Enter a 124 development shell with: 125 126 ``` 127 $ nix develop 128 ``` 129 130 Then do e.g.: 131 132 ``` 133 $ cabal repl ppad-eproc 134 ``` 135 136 to get a REPL for the main library. 137 138 ## References 139 140 - Waudby-Smith & Ramdas (2024), "[Estimating means of bounded random 141 variables by betting][wsr24]." JRSS-B. 142 - Ramdas, Grunwald, Vovk, Shafer (2023), "[Game-theoretic statistics 143 and safe anytime-valid inference][rgvs23]." Statistical Science. 144 - Shafer (2021), "[Testing by betting][shafer21]." JRSS-A. 145 146 [nixos]: https://nixos.org/ 147 [flake]: https://nixos.org/manual/nix/unstable/command-ref/new-cli/nix3-flake.html 148 [wsr24]: https://arxiv.org/abs/2010.09686 149 [rgvs23]: https://arxiv.org/abs/2210.01948 150 [shafer21]: https://arxiv.org/abs/1909.03807