Simplify Wasserstein distance between Gaussians with binary cost function

Question

Let $\mu_1$ and $\mu_2$ be 1D gaussian distributions with means $m_1$ and $m_2$ respectively and common variance $\sigma$. Let $\Omega$ be a closed subset of $\mathbb R^2$, and consider the cost function $c_\Omega:\mathbb R \times \mathbb R \rightarrow \{0, 1\}$ defined by $c_\Omega(x',x) = 1$ if $(x', x) \in \Omega; c(x',x) = 0$ otherwise. Further suppose that $\Omega$ is symmetric in the sense that $(x',x) \in \Omega \iff (x,x') \in \Omega$.

Now, consider the Wasserstein distance: $$ W_c(\mu_1,\mu_2) := \min_{\gamma \in \Pi(\mu_1,\mu_2)}\int_{(x',x) \in \mathbb R^2}c_\Omega(x',x)d\gamma(x',x) = \min_{\gamma \in \Pi(\mu_1,\mu_2)}\int_{(x',x) \in \Omega} d\gamma(x',x), $$ where $\Pi(\mu_1,\mu_2)$ is the set of all couplings of $\mu_1$ and $\mu_2$.

Question

• Is there an analytic formula for $W_c(\mu_1,\mu_2)$ (perhaps involving Gaussian integrals) ?

• Same question for the special case $\Omega = \{(x',x) \in \mathbb R^2 \mid |x'-x| \ge \alpha\}$, for some $\alpha > 0$.

Answer 1

This is an answer to the second question, for the particular choice of $\Omega$. In fact, in order to make the notation slightly simpler, let us assume that $\Omega = \{(x_1, x_2) : |x_1 - x_2| > \alpha\}$, with a strict inequality. By a simple approximation argument one easily sees that this change does not influence the answer.

---

Obviously, if $|m_1 - m_2| \leqslant \alpha$, then $W_c(\mu_1, \mu_2) = 0$: simply take $\gamma$ to be the distribution of $(X + m_1, X + m_2)$, where $X$ has Gaussian distribution with mean $0$ and variance $\sigma^2$.

---

Suppose that $|m_1 - m_2| > \alpha$, and assume with no loss of generality that $m_2 > m_1$. Let $f_m(x)$ be the probability density function of a Gaussian distribution with mean $m$ and variance $\sigma^2$. Define $\gamma$ in the following way (see the edit at the end of this answer for some intuition): $$ \begin{aligned} \gamma(dx_1, dx_2) & = \Bigl(\min\{f_{m_1}(x_1), f_{m_2 - \alpha}(x_1)\} \delta_{x_1 + \alpha}(dx_2) \\ & \qquad + \max\{0, f_{m_1}(x_1) - f_{m_2 - \alpha}(x_1)\} \delta_{m_1 + m_2 - x_1}(dx_2)\Bigr) dx_1 . \end{aligned} $$ This is a distribution concentrated on the line $$x_2 = x_1 + \alpha$$ and the half-line $$\begin{cases} x_2 = m_1 + m_2 - x_1, \\ x_2 \geqslant x_1 + \alpha. \end{cases}$$ It is immediate to see that $\gamma(dx_1, \mathbb{R}) = f_{m_1}(x_1) dx_1$, and it takes a while to find that $$ \begin{aligned} & \gamma(dx_1, dx_2) \\ & = \Bigl(\min\{f_{m_1}(x_1), f_{m_2 - \alpha}(x_1)\} \delta_{x_2 - \alpha}(dx_1) \\ & \qquad + \max\{0, f_{m_1}(x_1) - f_{m_2 - \alpha}(x_1)\} \delta_{m_1 + m_2 - x_2}(dx_1)\Bigr) dx_2 \\ & = \Bigl(\min\{f_{m_1}(x_2 - \alpha), f_{m_2 - \alpha}(x_2 - \alpha)\} \delta_{x_2 - \alpha}(dx_1) \\ & \qquad + \max\{0, f_{m_1}(m_1 + m_2 - x_2) - f_{m_2 - \alpha}(m_1 + m_2 - x_2)\} \delta_{m_1 + m_2 - x_2}(dx_1)\Bigr) dx_2 \\ & = \Bigl(\min\{f_{m_1 + \alpha}(x_2), f_{m_2}(x_2)\} \delta_{x_2 - \alpha}(dx_1) \\ & \qquad + \max\{0, f_{m_2}(x_2) - f_{m_1 + \alpha}(x_2)\} \delta_{m_1 + m_2 - \alpha - x_2}(dx_1)\Bigr) dx_2\end{aligned} $$ so that $\gamma(\mathbb{R}, dx_2) = f_{m_2}(x_2) dx_2$. It follows that $$ \begin{aligned} W_c(\mu_1, \mu_2) & \leqslant \int_{-\infty}^\infty \max\{0, f_{m_1}(x_1) - f_{m_2 - \alpha}(x_1)\} dx_1 \\ & = \int_{-\infty}^{(m_1 + m_2 - \alpha) / 2} (f_{m_1}(x_1) - f_{m_2 - \alpha}(x_1)) dx_1 \\ & = \mathbb{P}(X < \tfrac{m_2 - m_1 - \alpha}{2}) - \mathbb{P}(X < -\tfrac{m_2 - m_1 - \alpha}{2}) \\ & = \mathbb{P}(|X| < \tfrac{m_2 - m_1 - \alpha}{2}) , \end{aligned} $$ where $X$ has Gaussian distribution with mean $0$ and variance $\sigma^2$.

---

We claim that the above bound is optimal. Indeed, suppose that $(X_1, X_2)$ is a vector with marginals $f_{m_1}(x_1) dx_1$ and $f_{m_2}(x_2) dx_2$. Then $$ \begin{aligned} \mathbb{P}(|X_2 - X_1| > \alpha) & \geqslant \mathbb{P}(X_2 - X_1 > \alpha) \\ & \geqslant \mathbb{P}(X_2 > \tfrac{m_1 + m_2 + \alpha}{2}, \, X_1 < \tfrac{m_1 + m_2 - \alpha}{2}) \\ & \geqslant \mathbb{P}(X_2 > \tfrac{m_1 + m_2 + \alpha}{2}) - \mathbb{P}(X_1 \geqslant \tfrac{m_1 + m_2 - \alpha}{2}) \\ & = \mathbb{P}(X > \tfrac{m_1 - m_2 + \alpha}{2}) - \mathbb{P}(X \geqslant \tfrac{-m_1 + m_2 - \alpha}{2}) \\ & = \mathbb{P}(|X| < \tfrac{m_2 - m_1 - \alpha}{2}) , \end{aligned} $$ with $X$ as above. Thus, $$ W_c(\mu_1, \mu_2) \geqslant \mathbb{P}(|X| < \tfrac{m_2 - m_1 - \alpha}{2}) . $$

---

This gives the desired expression for $W_c(\mu_1, \mu_2)$: $$ W_c(\mu_1, \mu_2) = \mathbb{P}(|X| < \tfrac{m_2 - m_1 - \alpha}{2}) = 2 \Phi(\tfrac{m_2 - m_1 - \alpha}{2 \sigma}) - 1 , $$ where $\Phi$ is the cumulative distribution function of the standard Gaussian distribution.

---

Edit: The idea behind the coupling $\gamma$ constructed above is in fact quite simple. We like to have $X_1 = X_2 - \alpha$ with as high probability as possible. The "probability" that $X_1 = x_1$ must equal to $f_{m_1}(x_1)$, while the "probability" that $X_2 - \alpha = x_1$ must be equal to $f_{m_2 - \alpha}(x_1)$. Thus, we set $X_1 = X_2 - \alpha = x_1$ with "probability" $\min\{f_{m_1}(x_1), f_{m_2 - \alpha}(x_1)\}$.

This is now extended to a full coupling in a completely arbitrary way. It is quite easy to see that this is indeed possible (any sub-probability distribution $\gamma_0$ with marginals less than $f_{m_1}(x_1) dx_1$ and $f_{m_2}(x_2) dx_2$ can be extended to a full coupling of these measures), and in fact one easily finds an explicit expression by exploiting symmetry of Gaussians.

Answer 2

I agree with the comment by Mateusz that a simple expression is unlikely to exist for general sets $\Omega=:C$. For such sets, the best result is apparently as follows: $$W_c(\mu,\nu)=\sup\{\mu(A)-\nu(A^C)\colon A\subseteq\mathbb R, A\text{ closed}\}, $$ where $C$ is a nonempty open subset of $\mathbb R^2$, $c=1_C$, $$A^C:=\{y\in\mathbb R\colon\;\exists x\in A\ (x,y)\notin C\}, $$ and $\mu$ and $\nu$ are any (not necessarily Gaussian) probability measures over $\mathbb R$; see e.g. Theorem 1.27, p. 44.