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



Simplify Wasserstein distance between Gaussians with binary cost function
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.


