Closed-form formula for Wasserstein distance between uniform discrete distribution and discrete distribution with same support

Question

Let $x_1,\ldots,x_n$ be $n \ge 1$ distinct points in $\mathbb R^d$ and consider two discrete distributions on these points $\mu = (1/n)\sum_{i=1}^n\delta_{x_i}$, and $\nu = \sum_{i=1}^n\nu_i\delta_{x_i}$ with $\nu_1,\ldots,\nu_n \ge 0$ and $\sum_i \nu_i = 1$.

Let $(x_i,x_j) \mapsto c(x_i,x_j)$ be a distance on the $n$ points $x_1,\ldots,x_n$. For example, $c(x_i,x_j) := \|x_i-x_j\|_p$ for some $p \in [1,\infty)$.

Question

What's a closed form formula for the corresponding Wasserstein distance between $\mu$ and $\nu$ ?

Answer 1

Here is a general upper/lower bound on the Wasserstein distance between $\mu$ and $\nu$ based on a maximal coupling with respect to their total variation distance: $$ (1/2) \min_{x_i \ne x_j} c(x_i, x_j) \sum_{k=1}^n |1/n - \nu_k| \le \mathcal{W}(\mu,\nu) \le (1/2) \max_{x_i \ne x_j} c(x_i, x_j) \sum_{k=1}^n |1/n - \nu_k| \;. $$ More generally, the upper bound realized by a maximal coupling takes the form: $$ \mathcal{W}(\mu,\nu) \le \frac{\sum_{i \ne j} c(x_i, x_j) (\mu_j-\nu_j)^+ (\nu_i-\mu_i)^+}{\sum_k (\mu_k-\nu_k)^+}. $$ For completeness, the maximal coupling itself is explicitly given by: draw the first component $X$ from $\mu$ and then set the second component equal to: $$ Y=\begin{cases} X & \text{with probability $\frac{\nu(X)}{\mu(X)} \wedge 1$} \;, \\ \tilde{Y} & \text{otherwise} \;, \end{cases} $$ where $\tilde{Y}$ is a random variable (independent of all the preceding ones) drawn from the remaining probability suitably normalized $\tilde{\mu}(x) = \frac{(\nu(x) - \mu(x))^+}{\sum_k (\mu_k-\nu_k)^+}$.