Why does the Kolmogorov-Smirnov test work?

Question

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.

Answer 1

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

Answer 2

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}$.

Answer 3

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 against the null hypothesis, and for the alternate 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.