3
$\begingroup$

I have two probability distributions which each distribution has sum up to 1. I want to compute the distance between those two probability distributions. I want to use Earth Mover Distance to calculate the distance between those two distributions.

What I have found so far is the following, that $EMD(p_X,q_X)$ between distributions $p_X$ and $q_X$ is:

$$EMD(P,Q) = \frac{\sum^m_{i=1}\sum^n_{j=1} f_{ij}d_{ij}}{\sum^m_{i=1}\sum^b_{j=1} f_{ij}}$$

my question is, is there anyone has a mathematically proof that EMD is bounded distance. While two probability distributions have the same condition, sum up to 1. What's is the maximum possible value of the EMD that can be achieved (maximum bound)?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Are there any limitations on the distributions $p,q$ and definitions of $f_{ij}$ and $d_{ij}$? E.g. could $p$ or $q$ be a Cauchy distribution? (in which case you could make an example with infinite EMD by choosing a $p_X = \frac{2}{\pi (1+x)^2}$ and $q_X = 0$ for $x < 0$, $p_X=q_X = 0$ for $x=0$, and $p_X = 0$ and $q_X = \frac{2}{\pi (1+x)^2}$ for $x>0$) $\endgroup$
    – Sextus Empiricus
    Commented Jun 21, 2018 at 12:59
  • $\begingroup$ What happens with EMD when one distribution is for a random variable taking the value 1 with probability one, and the other distribution is for a random variable taking the value B with probability one, where B can be an arbitrarily large number? That can be a lot of distance to move that earth. You should probably link to your related question stats.stackexchange.com/questions/351947/… in which I commented Wasserstein distance can be as high as $\infty$. $\endgroup$
    – Mark L. Stone
    Commented Jun 21, 2018 at 13:13
  • $\begingroup$ Thanks @MarkL.Stone When I see the answer form Xi'an, he suggested me to Wasserstein distance that remains bound. Based on your comment, is that means there is no distance function that has static maximum bound, while two probability distributions have sum up 1? am I correct or wrong? $\endgroup$
    – user46543
    Commented Jun 22, 2018 at 0:10
  • 1
    $\begingroup$ Kolmogorov Distance is upper bounded by 1. Of course, it's very different than EMD and K-L Divergence. Also, Hellinger Distance and Total Variation Distance are bounded. $\endgroup$
    – Mark L. Stone
    Commented Jun 22, 2018 at 0:50
  • $\begingroup$ Hi @MarkL.Stone As I understand Kolmogorov Distance is used as for hypothesis testing. So, I need to put alfa and confidence interval. Not as usual distance function, that only need two distributions. $\endgroup$
    – user46543
    Commented Jun 22, 2018 at 8:19

1 Answer 1

Reset to default
3
$\begingroup$

The answer to your question as stated is no, unless your two random variables happens to be defined on a finite (or compact) metric space. But for real (or integer ...) valued random variables, certainly not. Detailed answers can be found from here: Earth Mover's Distance (EMD) between two Gaussians which analyzes (and lower-bounds) earth mover distance between two normal distributions.

It could also be easily answered from the interpretation "Earth Mover's Distance can be formulated and solved as a transportation problem. Suppose that several suppliers, each with a given amount of goods, are required to supply several consumers, each with a given limited capacity. For each supplier-consumer pair, the cost of transporting a single unit of goods is given. The transportation problem is then to find a least-expensive flow of goods from the suppliers to the consumers that satisfies the consumers' demand." from https://en.wikipedia.org/wiki/Earth_mover%27s_distance. Just move supplier and consumer at arbitrarily large distance ... Concretely, if both supplier and consumer lives on the surface of planet earth, an upperbound would be about 20000 km (that is an example of the compact case).

For information on such questions, a good source of information is in https://www.amazon.com/Encyclopedia-Distances-Michel-Marie-Deza/dp/3642309577

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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