Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Context: I want to compare the sample probability distributions (PDFs) of two datasets (generated from a dynamical system). These datasets depend on a set of parameters, and I want a concise way to evaluate the distance between the two PDFs over several different parameter regimes, ideally by a single number. For a fixed parameter regiume, my two sample PDFs are given by the vectors $x$ and $y$, where $x_i$ is the relative frequency of samples which lie in the $i$th bin.

One method I've seen is the Kolmogorov-Smirnov statistic, which is the maximum vertical distance between the cumulative distribution functions of the two datasets. This would work for my purposes, but I'm starting to think that the chi-squared distance will be better (at the very least I had heard of it). It is given by: $d(x,y) = \frac{1}{2}\sum_i \frac{(x_i-y_i)^2}{x_i+y_i}$. But this doesn't seem to make sense in the case where $x_i=y_i=0$, which seems like a fairly reasonable occurrence.

Any recommendations?

Edit: My first instinct was just to take the $L^2$ ($l^2$) norm of the difference of the two PDFs (sample PDFs). But then I thought the $L^1$ norm might be more suitable for a probability distribution. After looking a little further, I stumbled on the K-S and Chi-Squared distances.

share|improve this question
    
The Levy-Prokhorov metric? (see wikipedia) –  Anthony Quas Jul 25 '12 at 19:19
    
The Levy-Prokhorov metric is looks useful from an analytic point of view, but since I'm working with discrete sample distributions I don't think that will be helpful for me. –  Marc Kjerland Jul 25 '12 at 20:16
1  
Kullback-Leibler divergence(or the relative entropy) is the most commonly used one to measure the dissimilarity between two probability distributions. It also depends on what properties do you expect your dissimilarity measure to have. The following paper, which has got free access, might give you some idea: mdpi.com/1099-4300/10/3/261 . –  Ashok Jul 26 '12 at 5:46
    
Some proposals here: stats.stackexchange.com/questions/25764/… –  Stéphane Laurent Aug 17 '12 at 11:02
add comment

2 Answers

up vote 2 down vote accepted

In the first place the answer depends on the nature of your data (e.g., numerical continuous, numerical discrete, nominal etc.). In each of these cases the empirical measures on the range of your data have to be compared by using the corresponding specific methods. I presume that your values are reals (since you evoke the KS distance). In this case the most natural for your problem topology on the space of measures is weak, and by no means the norm (total variation) one, as empirical measures you deal with will typically be pairwise singular.

The weak topolgy, indeed, can be metrized by the "ad hoc" Levy-Prohorov metric, however, the transportation metric (which also metrizes the weak topology) is by far more canonical and appropriate in this situation (it was evoked in R Hahn's answer under the names of Earth-Mover's distance and Wasserstein metric). For instance, the KS distance between two distinct $\delta$-measures is always 1, their total variation distance is 2, whereas the transportation distance between them is equal to the distance between the corresponding points, so that it correctly reflects their similarity. Another advantage is that, unlike the LP metric, the transportation metric on the line can be easily computed explicitly (by using its dual description in terms of Lipschitz functions).

The metrics used in statistics, generally speaking, serve a purpose which is different from yours, and do not make much sense in your situation, when comparing two mutually singular empirical distributions. Most of the statistical distances only make sense for equivalent measures (like the Kullback-Leibler deviation). Of course, you can always discretize your data by using bins, however you will lose information about the data by making it "coarser" (which is OK for typical statistical purposes, but is not necessarily so for you). I do not see any reason to do that if one can efficiently work with the original data by metrizing the weak topology.

share|improve this answer
    
This was a very insightful and useful answer. Thank you! –  Marc Kjerland Jul 27 '12 at 19:49
    
The transportation metric is not a complete answer, because this distance between probability measures is induced by a distance on the real numbers, hence you firstly have to choose this later distance (the fact that different standard distance on $\mathbb{R}$ lead to the same topology has no interest in some applied mathematical problems) –  Stéphane Laurent Aug 17 '12 at 11:08
add comment

Total variation and Hellinger distance are two standard ways to measure this.

Kullback-Leibler divergence is another standard way, as would be general $f$-divergences.

The Earth-Mover's distance (also called the Wasserstein metric) is another option.

Bear in mind that your data gives an empirical cdf, so you can use any of the standard metrics for probability distributions notwithstanding the fact that you have a data sample in hand rather than a formula.

(Wiki has decent entries for all of these, which I may link to later.)

share|improve this answer
    
Thanks for the great info! I think I'll go with the Earth-Mover's distance. –  Marc Kjerland Jul 27 '12 at 19:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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