1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ Jul 30, 2019 at 21:09

2 Answers 2

3
+25
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks. Please could you explain the intuition behind the construction of your coupling $\gamma$ ? I really looks mysterious. $\endgroup$
    – dohmatob
    Jul 31, 2019 at 8:56
  • 1
    $\begingroup$ @dohmatob: I have just edited in some intuitions. The idea is quite simple, I think I rather failed to describe it clearly then. $\endgroup$ Jul 31, 2019 at 9:09
  • $\begingroup$ 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). $\endgroup$
    – dohmatob
    Jul 31, 2019 at 10:42
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.