# Motivation for Kolmogorov distance between distributions

There are many ways to measure how similar two probability distributions are. Among methods which are popular (in different circles) are:

1. the Kolmogorov distance: the sup-distance between the distribution functions;

2. the Kantorovich-Rubinstein distance: the maximum difference between the expectations w.r.t. the two distributions of functions with Lipschitz constant $1$, which also turns out to be the $L^1$ distance between the distribution functions;

3. the bounded-Lipschitz distance: like the K-R distance but the functions are also required to have absolute value at most $1$.

These have different advantages and disadvantages. Only convergence in the sense of 3. actually corresponds precisely to convergence in distribution; convergence in the sense of 1. or 2. is slightly stronger in general. (In particular, if $X_n=\frac{1}{n}$ with probability $1$, then $X_n$ converges to $0$ in distribution, but not in the Kolmogorov distance. However, if the limit distribution is continuous then this pathology doesn't occur.)

From the perspective of elementary probability or measure theory, 1. is very natural because it compares the probabilities of being in some set. A more sophisticated probabilistic perspective, on the other hand, tends to focus more on expectations than probabilities. Also, from the perspective of functional analysis, distances like 2. or 3. based on duality with some function space are very appealing, because there is a large set of mathematical tools for working with such things.

However, my impression (correct me if I'm wrong!) is that in statistics, the Kolmogorov distance is the usually preferred way of measuring similarity of distributions. I can guess one reason: if one of the distributions is discrete with finite support -- in particular, if it is the distribution of some real-world data -- then the Kolmogorov distance to a model distribution is easy to compute. (The K-R distance would be slightly harder to compute, and the B-L distance would probably be impossible in practical terms.)

So my question (finally) is, are there other reasons, either practical or theoretical, to favor the Kolmogorov distance (or some other distance) for statistical purposes?

-
I like the question, there may be already most of the possible answer in the question... do you have an idea of the type of answer/developpement you want? –  robin girard Jul 22 '10 at 11:18
Not very specifically. I'm quite ignorant of statistics and one of my reasons for asking is to learn which criteria statisticians would use to pick between different metrics. Since I did already describe one important practical advantage of 1 (you can actually compute it) I'm especially interested in theoretical motivations. Say, is the information provided by estimates of Kolmogorov distance frequently of direct use in applications? –  Mark Meckes Jul 22 '10 at 14:50
I forgot to end my previous comment with the more or less obvious: and if so, how? –  Mark Meckes Jul 22 '10 at 17:11
I just reread my long comment above and realized that the last question I raised is as much a practical consideration as theoretical. In any case, that's one of the kinds of issues I'd be interested to learn about. –  Mark Meckes Jul 23 '10 at 17:23
I know you did not meant to be exhaustive but you could add Anderson darling statistic (see en.wikipedia.org/wiki/Anderson%E2%80%93Darling_test). This made me remind of a paper fromo Jager and Wellner (see projecteuclid.org/…) which extands/generalises Anderson darling statistic (and include in particular higher criticism of Tukey)... –  robin girard Jul 25 '10 at 6:38

Mark,

the main reason of which I am aware for the use of K-S is because it arises naturally from Glivenko-Cantelli theorems in univariate empirical processes. The one reference I'd recommend is A.W.van der Vaart "Asymptotic Statistics", ch. 19. A more advanced monograph is "Weak Convergence and Empirical Processes" by Wellner and van der Vaart.

1. another measure of distance commonly used in univariate distributions is the Cramer-von Mises distance, which is an L^2 distance;
2. in general vector spaces different distances are employed; the space of interest in many papers is polish. A very good introduction is Billingsley's "Convergence of Probability Measures".

I apologize if I can't be more specific. I hope this helps.

-
Two quick notes on your notes. 1. The C-vM distance is precisely the L^2 cousin of the Kolmogorov (L^infinity) and (univariate) K-R (L^1) distances, and hence interpolates between them. 2. One advantage I didn't mention of the K-R and B-L distances is that they generalize more naturally to higher dimensional spaces. –  Mark Meckes Jul 26 '10 at 13:31
Regarding 1., that's correct. Regarding 2. In principle all of the above distances could carry over to R^n, however I don't know of popular non-parametric tests based on any distance. It would be interesting to know if there are any. –  gappy Jul 26 '10 at 20:18

Computational issues are the strongest argument I've heard one way or the other. The single biggest advantage of the Kolmogorov distance is that it's very easy to compute analytically for pretty much any CDF. Most other distance metrics don't have a closed-form expression except, sometimes, in the Gaussian case.

The Kolmogorov distance of a sample also has a known sampling distribution given the CDF (I don't think most other ones do), which ends up being related to the Wiener process. This is the basis for the Kolmogorov-Smirnoff test for comparing a sample to a distribution or two samples to each other.

On a more functional-analysis note, the sup norm is nice in that (as you mention) it basically defines uniform convergence. This leaves you with norm convergence implying pointwise convergence, and so you if you're clever about how you define your function sequences you can work within a RKHS and use all of the nice tools that that provides as well.

-

As a summary, my answer is : if you have an explicit expression or can figure out some how what your distance is measuring (what "differences" it gives weigth to), then you can say what it is better for. An other complementary way to analyse and compare such test is the minimax theory.

At the end some test will be good for some alternatives and some for others. For a given set of alternatives it is sometime possible to show if your test has optimal property in the worst case: this is the minimax theory.

Some details

Hence You can tell about the properties of two different test by regarding the set of alternative for which they are minimax (if such alternative exist) i.e. (using the word of Donoho and Jin) by comparing their "optimal detection boudary" http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1085408492.

Let me go distance by distance:

1. KS distance is obtained calculating supremum of difference between empirical cdf and cdf. Being a suppremum it will be highly sensitive to local alternatives (local change in the cdf) but not with global change (at least using L2 distance between cdf would be less local (Am I openning open door ?)). However, the most important thing is that is uses the cdf. This implies an asymetry: you give more importance to the changes in the tail of your distribution.

2. Wassertein metric (what you meant by Kantorovitch Rubinstein ? ) http://en.wikipedia.org/wiki/Wasserstein_metric is ubiquitous and hence hard to compare.

• For the particular case of W2 it has been uses in http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1017938923 and it is related to the L2 distance to inverse of cdf. My understanding is that it gives even more weight to the tails but I think you should read the paper to know more about it.
• For the case of the L1 distance between density function it will highly depend on how you estimate your dentity function from the data... but otherwise it seems to be a "balanced test" not giving importance to tails.

To recall and extend the comment I made which complete the answer:

I know you did not meant to be exhaustive but you could add Anderson darling statistic (see http://en.wikipedia.org/wiki/Anderson%E2%80%93Darling_test). This made me remind of a paper fromo Jager and Wellner (see http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1194461721) which extands/generalises Anderson darling statistic (and include in particular higher criticism of Tukey). Higher criticism was already shown to be minimax for a wide range of alternatives and the same is done by Jager and Wellner for their extention. I don't think that minimax property has been shown for Kolmogorov test. Anyway, understanding for which type of alternative your test is minimax helps you to know where is its strength, so you should read the paper above..

-
Yes, what I called the Kantorovitch-Rubinstein distance is also called the L^1 Wasserstein distance or W1. It goes by many other names too. –  Mark Meckes Jul 26 '10 at 13:37
Just to clarify for anyone unfamiliar with Wasserstein distances who reads this and gappy's answer: the L^2 Wasserstein distance (W2) is not the same as the Cramer-von Mises distance. –  Mark Meckes Jul 26 '10 at 18:55

I think you have to consider the theoretical vs applied advantages of the different notions of distance. Mathematically natural objects don’t necessarily translate well into application. Kolmogorov-Smirnov is the most well-known for application, and is entrenched in testing for goodness of fit. I suppose that one of the reasons for this is that when the underlying distribution $F$ is continuous the distribution of the statistic is independent of $F$. Another is that it can be easily inverted to give confidence bands for the CDF.

But it’s often used in a different way where $F$ is estimated by $\hat{F}$, and the test statistic takes the form $$\sup_x | F_n(x) - \hat{F}(x)|.$$ The interest is in seeing how well $\hat{F}$ fit the data and acting as if $\hat{F} = F$, even though the asymptotic theory does not necessarily apply.

-

I can't give you additional reasons to use the Kolmogorov-Smirnov test. But, I can give you an important reason not to use it. It does not fit the tail of the distribution well. In this regard, a superior distribution fitting test is Anderson-Darling. As a second best, the Chi Square test is pretty good. Both are deemed much superior to the K-S test in this regard.

-
From the point of view of functional analysis and measure theory the $L^p$ type distances do not define measurable sets on spaces of functions (infinite dimensional spaces loose countable additive in the metric ball coverings). This firmly disqualifies any sort of measurable interpretation of the distances of choices 2 & 3.
Of course Kolomogorov, being much brighter than any of us posting, especially including myself, anticipated this. The clever bit is that while the distance in the KS test is of the $L^0$ variety, the uniform norm itself is not used to define the measurable sets. Rather the sets are part of a stochastic filtration on the differences between the distributions evaluated at the observed values; which is equivalent to the stopping time problem.