An Improved Evaluation of Kolmogorov’s Distribution

Abstract

We propose a new algorithm for computing extreme probabilities of Kolmogorov's goodness-of-fit measure, Dn . This algorithm is an improved version of the method originally proposed by Wang, Tsang, and Marsaglia (2003) based on a result from Durbin (1973). The new algorithm keeps the same numerical precision of the Wang et al. (2003) method, but is more efficient: it features linear instead of quadratic space complexity and has better time complexity for a common range of input parameters of practical importance. The proposed method is implemented in the R package kolmim, which also includes an improved routine to perform one-sample two-sided exact Kolmogorov-Smirnov tests.