Return to Answer

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) - \nu(x) \wedge \mu(x)}{\sum_k (\mu_k-\nu_k)^+}$.

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)^+}$.

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) - \nu(x) \wedge \mu(x)}{\sum_k (\mu_k-\nu_k)^+}$.

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) - \nu(x) \wedge \mu(x)}{\sum_k (\mu_k-\nu_k)^+}$.

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| \;. $$

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) - \nu(x) \wedge \mu(x)}{\sum_k (\mu_k-\nu_k)^+}$.