Nested sampling for frequentist computation: fast estimation of small $p$-values

Abstract

We propose a novel method for computing $p$-values based on nested sampling (NS). The computational cost of NS scales as $\log^2 1/p$, which compares favorably to the $1/p$ scaling for Monte Carlo (MC) simulations. For significances greater than about $4\sigma$ in both a toy problem and a simplified resonance search, we show that NS requires orders of magnitude fewer simulations than ordinary MC estimates. This is particularly relevant for high-energy physics, which adopts a $5\sigma$ gold standard for discovery.