Motivation for Kolmogorov distance between distributions

Question

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?

Answer 1

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.

I'd add two quick notes:

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.

Answer 2

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" Link.

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 Link 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 Link) 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..

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

In short the uniform norm distance of choice 1 is preferable because the test it implies is equivalent to the stopping time problem, which itself produces computationally tractable probabilities. Where as choices 2 & 3 cannot define measurable subsets of functions.