What is the relationship of the EMD (Earth movers Distance) and total variation (and other probability measures)? I was trying to understand different methods for comparing probability distribution and saw the following paper/reference:
http://arxiv.org/abs/math/0209021
In it it defines and compares and explains some of the relationships between each probability measure. I was wondering if someone knew or understood better the relationships EMD has with other the other metrics?
The reason I am asking specifically about total variation and EMD is because I heard someone refer to them being the same thing, but I was not sure about it and after reading a little about both of them, I am a little skeptical they are the same thing in every case. Can anyone clarify that point? Maybe I was thinking there might be special probability distributions in  which they are the same ... Also if you have more knowledge in general about this, feel free to share that too (i.e. if you want to compare EMD to other measures in addition to total variation).
 A: The paper by Gibbs and Su you referenced is a great paper worth reading and rereading (I've done so several times now to good benefit). The key to understanding the relationship between the Total Variation (TV) distance and the Earth Mover's Distance (EMD) is the coupling construction in the Gibbs and Su paper (pg 7 equation (3) of TV subsection). Comparing that representation with the EMD (Wasserstein-Kantorovich) metric on page 8 you can see the representation using the Kantorovich-Rubinstein theorem (equation 4 on page 8 in Wasserstein-Kantorovich (WK) subsection), which looks similar to the coupling construction of the TV distance. To get them to match you've got to choose the distance function in the WK metric to be the Kronecker delta function $c(x_i,y_i)=\mathbb{1}(x_i \neq y_i)$ where $\mathbb{1}$ denotes an indicator (sometimes called characteristic) function. With this cost function and the constraints on the marginal probability laws (measures) then the expectation of this indicator function in the WK distance will result in $\Pr(X\neq Y)$ which is the cost function in the TV distance coupling characterizing formula. For finite state spaces (discrete & finite probability measures) you can calculate this solution using a linear program (LP). I've done this in a response to a question over on Cross Validated (CV). The question also have a posting with R code to calculate the TV (equivalently EMD/WK) distance in the problem asked by the post. Take a look and hopefully between this verbal description and that (admittedly long) post, you will see the relationship between TV distance and EMD. 
