4
$\begingroup$

If I want to conduct a two-sample Kolmogorov-Smirnov test - I understand I need to calculate the distance between two ECDFs multiple times across the length of the two curves, and then find the maximum distance between the two ECDFs as my test statistic

When and how exactly how many times is the distance computed between the two ECDFs?

Improve this question
$\endgroup$
6
  • $\begingroup$ It depends on the algorithm. But does it really matter? After all, there is an obvious way to find the statistic in $O(m+n)$ time for datasets of size $m$ and $n$ and--because it takes that much effort simply to read all the data--that asymptotic performance is the best possible. $\endgroup$
    – whuber ♦
    Commented Sep 30, 2016 at 16:15
  • $\begingroup$ @whuber Thanks. I think I understand. Are you saying that the fastest way to do this is to calculate the distance between the ECDFs for all m observations and all n observations - and take the maximum distance? Or have I got that wrong? $\endgroup$
    – TBradley
    Commented Sep 30, 2016 at 16:36
  • $\begingroup$ I can think of faster ways--but what is the point of improving on an algorithm that (a) already must take $O(m+n)$ time just to input the data and (b) is irrelevant when $m+n$ is much greater than a few thousand? $\endgroup$
    – whuber ♦
    Commented Sep 30, 2016 at 16:47
  • $\begingroup$ @whuber Ah sorry, maybe a little misunderstanding - I don't want to improve on existing algorithms. I merely want to better understand how existing algorithms work. I want to understand what is the minimum amount of times that the distance between the ECDFs must be calculated in order to be certain that the maximum distance has been sampled. Presumably if I just calculated one distance (with e.g. m=n=100) it is unlikely that this would be the true maximum Maybe the minimum amount of times D has to be computed is merely m + n? $\endgroup$
    – TBradley
    Commented Sep 30, 2016 at 17:03
  • $\begingroup$ The maximum number of times $D$ would need to be computed is $m+n$. After all, there are only $m+n$ data points and each one of them only has to be compared to two others (at most). But I was incorrect in asserting the algorithm is $O(m+n)$: the simplest implementations require the data to be sorted, making it $O(log(m+n))$. Thus (in principle) there is an opportunity to make an asymptotic improvement. $\endgroup$
    – whuber ♦
    Commented Sep 30, 2016 at 17:31

1 Answer 1

Reset to default
2
$\begingroup$

When you calculate a Kolmogorov-Smirnov statistic you find the maximum distance between cdfs. In the case of the two-sample statistic, it's the maximum distance between two empirical cdfs.

At the extreme left (to the left of any data points), the distance between cdfs is 0, and at the extreme right (to the right of all data points) the distance is also 0. To find the largest of the distances in between those, at most you need to compute the distance when it changes. Here's an illustrative example:

Two sample KS test showing locations of changes in distance between the ECDFs

As we can see the distance between cdfs only changes at the data points. As a result if the two sample sizes are $m$ and $n$, the largest number of changes we'd have to consider would be $m+n$. However, the very last change will be to $0$, so we don't need to check that one, making it at most $m+n-1$ places we need to consider the difference in values.

(It may be fewer than that in some situations - for example if there are ties in the data, there's only a need to consider the total number of distinct values.)

At an observation from the first sample, $F_1-F_2$ (note this is not presently $|F_1-F_2|$, it's a signed quantity) will increase by $1/m$ and at an observation from the second sample, $F_1-F_2$ will decrease by $1/n$.

In some cases it's possible to know that the largest $D$ identified so far will not be exceeded at the next change or even the next several changes, in which case it may in principle be possible in some particular situations to reduce the number of comparisons from $m+n-1$ to some smaller number.

However, to my knowledge actual implementations generally calculate the difference at every data point (often including the redundant calculation at the last observation of the combined sample).

As an example the implementation in R calculates the difference at all $m+n$ values; no attempt is made to try to reduce it (not least because it's likely to be slower to try to reduce that calculation than simply to do the calculation).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.