# Why does the Kolmogorov-Smirnov test work?

In reading about the 2-sample KS test, I understand exactly what it is doing but I don't understand why it works.

In other words, I can follow all the steps to compute the empirical distribution functions, find the maximum difference between the two to find the D-statistic, calculate the critical values, convert the D-statistic to a p-value etc.

But, I have no idea why any of this actually tells me anything about the two distributions.

Someone could have just as easily told me that I need jump over a donkey and count how fast it runs away and the if the velocity is less than 2 km/hr then I reject the null-hypothesis. Sure I can do what you told me to do, but what does any of that have to do with the null-hypothesis?

Why does the 2-sample KS test work? What does computing the maximum difference between the ECDFs have to do with how different the two distributions are?

Any help is appreciated. I am not a statistician, so assume that I'm an idiot if possible.

• Welcome to CV, Darcy! Great question! – Alexis Nov 28 '18 at 18:00
• Jump over a donkey... :) – Richard Hardy Nov 29 '18 at 12:48

Basically, the test is consistent as a direct result of the Glivenko Cantelli theorem, one of the most important results of empirical processes and maybe statistics.

GC tells us that the Kolmogorov Smirnov test statistic goes to 0 as $$n \rightarrow \infty$$ under the null hypothesis. It may seem intuitive until you grapple with real analysis and limit theorems. This is a revelation because the process can be thought of as an uncountably infinite number of random processes, so the laws or probability would lead one to believe that there is always one point which could exceed any epsilon boundary but no, the supremum will converge in the long run.

How long? Mmyyeeaa I don't know. The power of the test is kind of dubious. I'd never use it in reality.

http://www.math.utah.edu/~davar/ps-pdf-files/Kolmogorov-Smirnov.pdf

• +1 Hi AdamO! Got a one to two sentence take on the power being "kind of dubious?" I would love that perspective (I have gathered that the test is considered easily "overpowered"). – Alexis Nov 28 '18 at 17:59
• @Alexis The test is not overpowered, IRL we almost never expect the null to be true, rather we just don't care whether the 99.999-th percentile differs by 0.1 between $F_1$ and $F_2$., so whenever I see $p > 0.05$ from the KS test, all I think is, "that's a false negative" and whenever I see $p < 0.05$ I think "whoop-dee-do so what can you say about that?". Tests of the strong null hypothesis $F_1 = F_2$ aren't a compelling way of presenting scientific evidence. – AdamO Nov 28 '18 at 19:18
• Ok. I get yer concern with hypothesis tests for difference. But does your concern about power arise from the simple ontological belief that $F_{1}$ almost surely $\ne F_{2}$? or is there something more mathy about asymptotics or something else in there? – Alexis Nov 28 '18 at 19:49
• @Alexis no, I have no concerns with the mathematics of the test. In fact, I think it's quite elegant and the limit theorem result is very impressive. – AdamO Nov 29 '18 at 4:15
• @Alexis I will say, in settings where it is possible for $F_1$ to be exactly equal to $F_2$, the test can be pretty handy. I agree that not a lot of substantive scientific applications fit that bill, but in a statistical computing context where you want to validate that some software you've written is generating pseudo random numbers from some known distribution, it's quite useful. It effectively codifies the intuition you'd get from looking at probability plots. – jcz Nov 29 '18 at 15:01

We have two independent, univariate samples:

\begin{align} X_1,\,X_2,\,...,\,X_N&\overset{iid}{\sim}F\\ Y_1,\,Y_2,\,...,\,Y_M&\overset{iid}{\sim}G, \end{align} where $$G$$ and $$F$$ are continuous cumulative distribution functions. The Kolmogorov-Smirnov test is testing \begin{align} H_0&:F(x) = G(x)\quad\text{for all } x\in\mathbb{R}\\ H_1&:F(x) \neq G(x)\quad\text{for some } x\in\mathbb{R}. \end{align} If the null hypothesis is true, then $$\{X_i\}_{i=1}^N$$ and $$\{Y_j\}_{j=1}^M$$ are samples from the same distribution. All it takes for the $$X_i$$ and the $$Y_j$$ to be draws from different distributions is for $$F$$ and $$G$$ to differ by any amount at at least one $$x$$ value. So the KS test is estimating $$F$$ and $$G$$ with the empirical CDFs of each sample, honing in on the largest pointwise difference between the two, and asking if that difference is "big enough" to conclude that $$F(x)\neq G(x)$$ at some $$x\in\mathbb{R}$$.

An intuitive take:

The Kolmogorov-Smirnov test relies pretty fundamentally on the ordering of observations by distribution. The logic is that if the two underlying distributions are the same, then—dependent on sample sizes—the ordering should be pretty well shuffled between the two.

If the sample ordering is "unshuffled" in an extreme enough fashion (e.g., all or most the observations in distribution $$Y$$ come before the observations in distribution $$X$$, which would make the $$D$$ statistic much larger), that is taken as evidence that the null hypothesis that the underlying distributions are not identical.

If the two sample distributions are well shuffled, then $$D$$ won't have an opportunity to get very big because the ordered values of $$X$$ and $$Y$$ will tend to track along with one another, and you won't have enough evidence to reject the null.

• Agree, but would add the part from the answer of @AdamO. That is, with n→∞ the smallest differences in distributions will be detected. In other words, with large sample sizes (n), it's quite unlikely to expect insignificant test results in many fields. – Amonet May 11 '20 at 12:16