18
$\begingroup$

The Kolmogorov–Smirnov distribution is known from the Kolmogorov–Smirnov test. However, it is also the distribution of the supremum of the Brownian bridge.

Since this is far from obvious (to me), I would like to ask you for an intuitive explanation of this coincidence. References are also welcome.

Improve this question
$\endgroup$
2
  • $\begingroup$ @GaBorgulya: What did you change? $\endgroup$ – Rasmus Jun 14 '11 at 16:24
  • $\begingroup$ See here and here. $\endgroup$ – cardinal Jun 18 '11 at 1:58
13
$\begingroup$

$\sqrt{n}\sup_x|F_n-F|=\sup_x|\frac{1}{\sqrt{n}}\sum_{i=1}^nZ_i(x)| $

where $Z_i(x)=1_{X_i\leq x}-E[1_{X_i\leq x}]$

by CLT you have $G_n=\frac{1}{\sqrt{n}}\sum_{i=1}^nZ_i(x)\rightarrow \mathcal{N}(0,F(x)(1-F(x)))$

this is the intuition...

brownian bridge $B(t)$ has variance $t(1-t)$ http://en.wikipedia.org/wiki/Brownian_bridge replace $t$ by $F(x)$. This is for one $x$...

You also need to check the covariance and hence it still is easy to show (CLT) that for ($x_1,\dots,x_k$) $(G_n(x_1),\dots,G_n(x_k))\rightarrow (B_1,\dots,B_k)$ where $(B_1,\dots,B_k)$ is $\mathcal{N}(0,\Sigma)$ with $\Sigma=(\sigma_{ij})$, $\sigma_{ij}=\min(F(x_i),F(x_j))-F(x_i)F(x_j)$.

The difficult part is to show that the distribution of the suppremum of the limit is the supremum of the distribution of the limit... Understanding why this happens requires some empirical process theory, reading books such as van der Waart and Welner (not easy). The name of the Theorem is Donsker Theorem http://en.wikipedia.org/wiki/Donsker%27s_theorem ...

Improve this answer
$\endgroup$
5
  • $\begingroup$ Shouldn't we apply the CLT to all finite-dimensional marginal distributions? $\endgroup$ – Rasmus Aug 11 '10 at 15:26
  • $\begingroup$ you asked for an intuitive answer :) also I choose not to bother you with the tricky mathematical part which is to show that the convergence for all t implies the convergence (in law) of the supremum... do you want me to complete the answer ? $\endgroup$ – robin girard Aug 11 '10 at 16:11
  • $\begingroup$ Dear robin girard, I think your answer is fine as it stands. Thank you! $\endgroup$ – Rasmus Aug 11 '10 at 17:16
  • 1
    $\begingroup$ the difficult part actually is to show weak convergence. The convergence of supremums then follows directly from continuous mapping theorem. This result can be found in Billingsley's "Convergence of Probability Measures". Van der Vaart and Wellner give more general result and their book is really, really tough :) $\endgroup$ – mpiktas Feb 10 '11 at 10:58
  • $\begingroup$ @robingirard I personally would love to see a "complete answer" with all the "tricky mathematical part[s]" $\endgroup$ – epp Jul 5 '17 at 23:28
6
$\begingroup$

For Kolmogorov-Smirnov, consider the null hypothesis. It says that a sample is drawn from a particular distribution. So if you construct the empirical distribution function for $n$ samples $f(x) = \frac{1}{n} \sum_i \chi_{(-\infty, X_i]}(x)$, in the limit of infinite data, it will converge to the underlying distribution.

For finite information, it will be off. If one of the measurements is $q$, then at $x=q$ the empirical distribution function takes a step up. We can look at it as a random walk which is constrained to begin and end on the true distribution function. Once you know that, you go ransack the literature for the huge amount of information known about random walks to find out what the largest expected deviation of such a walk is.

You can do the same trick with any $p$-norm of the difference between the empirical and underlying distribution functions. For $p=2$, it's called the Cramer-von Mises test. I don't know the set of all such tests for arbitrary real, positive $p$ form a complete class of any kind, but it might be an interesting thing to look at.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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