Kolmogorov-Smirnov two-sample $p$-values

I am using the Kolmogorov–Smirnov two-sample test to compare distributions, and I noticed a $p$-value is frequently reported as the test statistic. How is this $p$-value determined? I know it's the probability of obtaining a result at least as large as the one obtained, but how is this $p$-value determined given this is a nonparametric test? That is, we can't assume Gaussian fluctuations in the distribution and compute the $p$-value using a $t$-test.

Thanks!

-
The Kolmogorov-Smirnov statistic (over the class of distributions of continuous random variables) is distribution-free. So, the distribution of the test statistic does not depend on the underlying distribution of the data (under the null hypothesis). –  cardinal Oct 24 '11 at 19:31
@Cardinal's point is made in a comment in the Wikipedia entry. Note that the distribution of the test statistic is asymptotic (that is, valid when the smaller sample size is itself large); it likely does depend on the common underlying distribution for small samples. –  whuber Oct 24 '11 at 21:15
@whuber: I fear I don't quite understand your comment and I don't want to misinterpret it. Certainly, the distribution in finite samples will not be exactly the same as the asymptotic distribution, but that does not prevent the statistic from being distribution-free for every fixed sample size $n$ (really $(n_1,n_2)$ since the sizes may differ). [cont] –  cardinal Oct 25 '11 at 0:27
@whuber: ...Let $X_i \sim F$ and $Y_i \sim G$ be independent iid sequences. Then $n \hat{F}_n(x) = |\{i: X_i \leq x\}| = |\{i: F(X_i) \leq F(x)\}|$ and $n \hat{G}_n(x) = |\{i: Y_i \leq x \}| = |\{i: G(Y_i) \leq G(x)\}|$. So, with the aforementioned assumption that $F$ and $G$ are continuous distributions, under the null hypothesis $F=G$, we see that $\sup |\hat{F}_n(x) - \hat{G}_n(x)|$ is equal in distribution to the same statistic obtained from two independent $\mathcal U(0,1)$ samples of the same size. –  cardinal Oct 25 '11 at 0:33
@cardinal Thank you; that is a helpful observation. At the same time it shows why the p-value is independent of the distributional assumption. You should copy this into a reply to the question. –  whuber Oct 25 '11 at 0:39
show 1 more comment

Under the null hypothesis, the asymptotic distribution of the two-sample Kolmogorov–Smirnov statistic is the Kolmogorov distribution, which has CDF

$$\operatorname{Pr}(K\leq x)=\frac{\sqrt{2\pi}}{x}\sum_{i=1}^\infty e^{-(2i-1)^2\pi^2/(8x^2)} \>.$$

The $p$-values can be calculated from this CDF - see Section 4 and Section 2 of the Wikipedia page on the Kolmogorov–Smirnov test.

You seem to be saying that a non-parametric test statistic shouldn't have a distribution - that's not the case - what makes this test non-parametric is that the distribution of the test statistic does not depend on what continuous probability distribution the original data come from. Note that the KS test has this property even for finite samples as shown by @cardinal in the comments.

-
(+1) I might suggest a small tweak to your last sentence. The test statistic is distribution-free even in finite samples (though it won't be the same as the asymptotic distribution). So, this distribution-free property is what makes the test statistic nonparametric. Note that there are lots of examples where the asymptotic distribution does not depend on the underlying continuous distribution (just think about the CLT), so, unless I'm mistaken, I don't believe that's the core feature here. :) –  cardinal Feb 21 '12 at 13:30
I made the correction but the more I think about it the more I wonder how you know that the statistic truly doesn't depend on the original distribution of the data in finite samples - can you say any more about this @cardinal? –  Macro Feb 21 '12 at 14:04
Sure. See the fourth comment (my third one) to the question above. –  cardinal Feb 21 '12 at 14:21
I see! very cool and simple - thanks cardinal –  Macro Feb 21 '12 at 15:26