Dr Ivan D. Reid (School of Design and Engineering - Brunel University, UK)
Goodness-of-fit statistics measure the compatibility of random samples against some theoretical probability distribution function. The classical one-dimensional Kolmogorov-Smirnov test is a non-parametric statistic for comparing two empirical distributions, which defines the largest absolute difference between the two cumulative probability distribution functions as a measure of disagreement. Adapting this test to more than one dimension is a challenge because there are 2k-1 independent ways of defining a cumulative probability distribution function when k dimensions are involved. However there are many applications in experimental physics where comparing two-dimensional data sets is important. In this paper we discuss Peacock's version  of the Kolmogorov-Smirnov test for two-dimensional data sets which computes the differences between cumulative probability distribution functions in 4n2 quadrants and runs in O(n^3), for a sample of size n. We also discuss Fasano and Franceschini's variation  of Peacock's test that runs in O(n^2), Cooke's algorithm for Peacock's test and ROOT's version of the two-dimensional Kolmogorov-Smirnov. We establish a lower-bound limit on the work for computing Peacock's test in W(n2lgn), which contradicts Cooke's claim that it possible to perform this test with an O(nlgn) algorithm. We also establish a lower-bound limit of W(nlgn) for Fasano and Franceschini's test, and present an optimal sequential algorithm for it. We finally discuss experimental results comparing two parallel algorithms implementing Peacock's test and an optimal algorithm for Fasano and Franceschini's test, and contrast these with the algorithm in ROOT which is based on the calculation of a mean of two one-dimensional Kolmogorov-Smirnov tests. References  A. Cooke. The muac algorithm for solving 2d ks test. http://www.acooke.org/jara/muac/algorithm.html.  G. Fasano and A. Franceschini. A multidimensional of the Kolmogorov-Smirnov test. Monthly Notices Royal Astronomy Society, 225:155-170, 1987.  J. A. Peacock. Two-dimensional goodness-of-fit testing in astronomy. Monthly Notices Royal Astronomy Society, 202:615-627, 1983.
|Submitted on behalf of Collaboration (ex, BaBar, ATLAS)