Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Efficient Algorithms for the Kolmogorov-Smirnov and Lilliefors Tests t

IP.com Disclosure Number: IPCOM000128516D
Original Publication Date: 1974-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 7 page(s) / 24K

Publishing Venue

Software Patent Institute

Related People

Teofilo Gonzalez: AUTHOR [+4]

Abstract

A linear time algorithm to compute the holmogorov-Smirnov and Lilliefors test statistics is. presented. An Approximation algorithm with reduced memory and time requirements is also presented. Keywords and Phrases., Itolznogorov-Smirnov test, Lilliefors test, exact and approximate algorithms time and space complexity. CR Categories 5.2595.5

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 24% of the total text.

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Efficient Algorithms for the Kolmogorov-Smirnov and Lilliefors Tests t

by Teofilo Gonzalez Sartaj Sahni and William R. Frauta

Computer, Information, and Control Sciences Department Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Technical December, 1974 tThis research was supported 3n part by NSF grant DCR 74-10081

Cover design courtesy of Ruth and Jay Leavitt

Efficient Algorithms for the Kolmogorov-Smirnov and Lilliefors Tests by Teofilo Gonzalez, Sartaj Sahni and William R. Franca Department of Computer Science University of Minnesota

Abstract

A linear time algorithm to compute the holmogorov-Smirnov and Lilliefors test statistics is. presented. An Approximation algorithm with reduced memory and time requirements is also presented.

Keywords and Phrases., Itolznogorov-Smirnov test, Lilliefors test, exact and approximate algorithms time and space complexity.

CR Categories 5.2595.5 >

1. Introduction

The Kolmogorov-Smirnov and Lilliefors tests allow us to evaluate the hypothesis that a collected data set, i.e., a random sample X1,...,Xn, was drawn from a specified continuous distribution function F(y,). For both tests, a determination is made of the numeric difference between the specified distribution function F(X), and the sample distribution function S(X) as defined by equation 1.1. If the sample, Xl,...,Xn, has been sorted into nondecrea3ing order so that

(Equation Omitted)

then the Kalmogorov--Smirnov statistics Kmax (maximum positives mar (maximum negative) and Kmax (maximum absolute) deviations are computed by formulas 1.2 .

(Equation Omitted)

The distribution functions of Kmax ,K~x and Kmax are known and tabulated. Tie accept the null hypothesis that the sample was indeed drawn frog. the distribution F(X) if the .statistics computed do not exceed the critical values tabulated far the level of significance selected. For certain F(X), (see [4), C5]) tabulated values of the test statistic distributions are available for the case where the actual parameters of F(X) have been replaced by estimates computed fromvthe. sample. The test also has~application far certain spectraivtests; see for example, [2, p. 197]..

University of Minnesota Page 1 Dec 31, 1974

Page 2 of 7

Efficient Algorithms for the Kolmogorov-Smirnov and Lilliefors Tests t

> Previous algorithms ([3], [&] and [7] for computing these test.statistics are essentially identical to algorithm K below:

Algorithm

(Equation Omitted)

Knuth's algorithm for Kolmogorov-Smirnov test statistics [3] pp. 44// Step 1 obtain the n observations

(Equation Omitted)

Step 2 sort them so that

(Equation Omitted)

Step 3 Compute K+ , K and Kmax using equation 1.2. max ma~ Since, step 2 sorts the observations, it requires 0(n log n) time. The remainder of the algorithm takes 0(n) time (assuming F(X) may be computed in a constant amount o£ time 0(1)). Hence, the total time required is 0(n log n).

The algor...