Distance metric between two sample distributions (histograms)

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.

-
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
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

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.

-
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

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

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