Simplify Wasserstein distance between Gaussians with binary cost function

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

• I wrote an answer to you second question below. Regarding the first one, I doubt there is an answer with no further assumptions on $\Omega$. At the very least, one should assume that $\Omega = \{(x_1, x_2) : |x_1 - x_2| \geqslant \phi(x_1 + x_2)\}$ for some $1$-Lipschitz $\phi$. Jul 30, 2019 at 21:09

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.

• Thanks. Please could you explain the intuition behind the construction of your coupling $\gamma$ ? I really looks mysterious. Jul 31, 2019 at 8:56
• @dohmatob: I have just edited in some intuitions. The idea is quite simple, I think I rather failed to describe it clearly then. Jul 31, 2019 at 9:09
• Thanks :). In the meanwhile, I'd come up with a somewhat synthetic solution to a generalization of the second part of my original question. See post below. Would like to know what you think. N.B.: It's possible my answer has a loophole due to an unjustified step (b). Jul 31, 2019 at 10:42

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.

• Thanks. I had already managed to obtain this general expression, from the "Strassen formula" you referred me to on another question :) Aug 2, 2019 at 8:24