Kantorovich distance: discrete distributions Let $\mu,\nu$ be two discrete distributions on $\Bbb R$, and for simplicity assume that each takes only a finite number of values. For example, $\mu$ gives probabilities $p_i$ to points $x_i$ and $\nu$ gives probabilities $q_j$ to points $x_j$. The Kantorovich distance between them can be computed as 
$$
  \int_{-\infty}^\infty |F_\mu(t) - F_\nu(t)|\mathrm dt.
$$
Is there a way to simplify this expression in my setting?
 A: $\newcommand{\d}{\mathrm{d}}$In fact the Wasserstein distance between two probability measures $P$ and $Q$ on a measurable space $(\Omega, \mathcal{F})$ is defined as follows (I'll give the definition of the distance of order $1$):
$$
W(P,Q) = \inf_{\mu} \left\{ 
\int_{\Omega\times \Omega} |x-y|\d \mu
\left|
  \begin{array}{l}
   \mu: \text{ prob. measure on } (\Omega \times \Omega, \mathcal{F}\otimes \mathcal{F})\\
\text{with marginals } P, Q
  \end{array}
\right.
\right\}
$$
In the definition $\Omega\times \Omega$ is the product probability space. Notice that we may extend the definition so that $P$ is a measure on a space $(\Omega, \mathcal{F})$ and $Q$ is a measure on $(\Omega', \mathcal{F}')$.
Let us now see how the above applies in the case of discrete sample spaces. For generality, let us assume that $P$ is a measure on $(\Omega, \mathcal{F})$ where $\Omega=\{\omega_i\}_{i=1}^{s}$ and $Q$ is a measure on $(\Omega', \mathcal{F}')$ where $\Omega'=\{\omega_i'\}_{i=1}^{s'}$ - here the two spaces are not required to have the same cardinality.
Then, the distance between $P$ and $Q$ becomes
$$
W(P,Q) = \inf_{\{\lambda_{i,j}\}, i, j} \left\{
\sum_{i=1}^{s}\sum_{j=1}^{s'}\lambda_{i,j} |\omega_i - \omega_j'|: 
\sum_{i=1}^{s}\lambda_{i,j} = q_j, \sum_{j=1}^{s'}\lambda_{i,j} = p_i,
\lambda_{i,j}\geq 0
\right\}
$$
This is a linear program, so it is easy to solve computationally.
A: OP wrote $\int_{-\infty}^\infty |F_\mu(t) - F_\nu(t)|\mathrm dt$, which a closed form for the $1$-Wasserstein distance in the $1$-D case, with ground cost $c(x,y)=|x-y|$.
In the discrete case where $\mu = \sum_{i=1}^np_i \delta_{x_i}$ and $\nu=\sum_{j=1}^m q_j \delta_{y_i}$, the Wasserstein distance is computable in $O(n\log n + m\log m)$. Indeed $F_\mu$ and $F_\nu$ are two step functions and once the support points are sorted, the integral is computable as a finite sum.
In the special case where $n=m$ and the weights are uniform (i.e equal to $\frac 1n$) the $p$-Wasserstein has the nice closed form $\left(\frac 1n \sum_{i=1}^n |x_{\sigma(i)} -y_{\tau(i)}|^p  \right)^{\frac 1p}$ where $\sigma$ is a permutation that sorts the $x_i$ and $\tau$ is a permutation that sorts the $y_j$. 
