Fast calculation of p-values for one-sided Kolmogorov-Smirnov type statistics

We present a method for computing exact p-values for one-sided statistics of the Kolmogorov-Smirnov family. This includes the Higher Criticism statistic, one-sided weighted Kolmogorov-Smirnov statistics, and the one-sided Berk-Jones statistics. For a sample size of 10,000 our method takes merely 0.15 seconds to run and it can scale to sample sizes in the hundreds of thousands. This allows practitioners working on big data sets to use exact finite-sample computations instead of approximation schemes. Our work has other applications in statistics, including power analysis, finding $\alpha$-level thresholds, and the construction of confidence bands for the empirical distribution function. The method is based on a reduction to the boundary-crossing probability of a pure jump process and is also applicable to fields outside of statistics, for example financial risk modeling.