# wasserstein distance between distributions with bounded ratio

Let $p$ and $q$ be probability distributions on a metric space $X=(X, d)$ with densities $dp$ and $dq$, such that there exists $0 < \alpha < \beta < \infty$ satisfying

$$\alpha d p \le dq \le \beta dp .$$

What is an upper bound for the Wasserstein distance $W_d(p,q)$ ?

Notes: $W_d(p, q) := \sup_{\|f\|_{\text{Lip}} \le 1} |\mathbb E_{x \sim p}[f(x)] - \mathbb E_{x \sim q}[f(x)]|$

# Update

It's well known (e.g see Gabe K's response below or Theorem 4 of this paper) that

$$W_d(p, q) \le \operatorname{diam}(X)\operatorname{TV}(p, q).$$

Thus if $X$ has finite diameter, it suffices to bound $\operatorname{TV}(p, q)$.

Recall the definition of total variation,

$$\operatorname{TV}(p, q) := \sup_{A \subseteq X} \left|\int_A dq-\int_A dp\right|.$$ Now, for any $A \subseteq X$, one has $\int_A dq - \int_A dp \ge \int_A(\alpha-1)dp = (\alpha-1)p(A).$ Similarly, one has $\int_A dq - \int_A dp \le (\beta-1)p(A)$. Thus $$\left|\int_A dq - \int_A dp \le (\beta-1)p(A)\right| \le \max(1-\alpha,\beta-1)p(A) \le \max(1-\alpha,\beta-1),$$ and so $\operatorname{TV}(p,q) \le \max(1-\alpha,\beta-1)$. Putting things together, we get

$$W_d(p,q) \le \operatorname{diam}(X)\max(1-\alpha,\beta-1).$$

# Case of infinite diameter

In case of infinite diameter assuming that $p$ or $q$ satisfies a Talagrand transportation-cost inequality, i.e

$$W_{d,2}(p,r)\le \sqrt{(2/\rho)\operatorname{kl}(r\|p)}$$ for some $\rho > 0$ and for any distribution $r$ on $X$ relatively continuous w.r.t $p$,

with a similar story for $q$ (e.g for standard Gaussian, this holds with $\rho=1$), allows us to still get an upper bound, namely $$W_{d,2}(p,q) \le \sqrt{2\min (\beta\log(\beta)/\rho_p,(1/\alpha)\log(1/\alpha)/\rho_q)}.$$

• Do you want a bound using only $\alpha$ and $\beta$? – gerw Aug 29 '18 at 11:54
• Ya sure, a bound in terms of $\alpha$ and $\beta$ (and perhaps a the diameter of the space $X$ w.r.t $p$ ?!) :) – dohmatob Aug 29 '18 at 12:15
• Perhaps the dual form of $W_d(p,q)=\int_0^1 |F^{-1}_p(u)-F^{-1}_q(u) | \mathrm{d}u$ is useful here? – Jan Aug 29 '18 at 13:10
• Nope. That's only valid in 1 dimension. – dohmatob Aug 29 '18 at 13:12
• Does "densities" here just mean Radon-Nikodym derivatives with respect to some (unspecified, but the same for p and q) measure on $(X,d)$? – Steve Aug 29 '18 at 14:44

Any estimate will need to incorporate the diameter of $X$. To see this, consider the interval $[0,L]$ and the distribution with density,

$$\begin{cases} \frac{2}{L} & 0 \leq x \leq L/3 \\ \frac{1}{2L} & L/3 \leq x \leq L \\ \end{cases}$$

One can calculate the distance from the uniform distribution $1/L$ using the dual formulation of the Wasserstein distance, and it blows up as $L$ goes to infinity. Therefore, we cannot hope for an estimate solely in terms of $\alpha$ and $\beta$.

However, assuming a bound on the diameter $D$ of $X$, then we can say more. With $\alpha$ and $\beta$, we can derive a bound on $\delta(p,q)$ the total variation distance between $p$ and $q$. One possible transfer plan from $p$ to $q$ is to move the excess mass of $p$ to $q$, fixing the overlap. The total mass to be moved then is $\delta(p,q)$, and the cost to move the mass is no more than $D^d$. Skipping some derivations, this shows that the Wasserstein 2-distance is bounded by $D \sqrt{ \delta(p,q)}$, so this gives your desired result. This can be generalized to the other Wasserstein metrics as well.

• sure. Thanks for the response (upvoted). Sure, I suspected it involve the diameter of $X$ w.r.t to $p$. See my comment section above. More precisely, it would involve something like $\sup_{x_0} \mathbb E_{x \in p} d(x,x_0)$ (which is $\le D$). – dohmatob Aug 29 '18 at 15:03
• OK, i can workout $TV(p,q) \le \max(1-\alpha,\beta-1)$ and so $W_d(p,q) \le \max(1-\alpha,\beta-1)\operatorname{diam}(X)$ – dohmatob Aug 29 '18 at 17:16
• Also this document provides numerous useful inequalities between metrics on probability measures math.hmc.edu/~su/papers.dir/metrics.pdf. In general to upper bound $W$ metric with another metric, you need an upper bound on the diameter of the metric space. – dohmatob Aug 29 '18 at 17:19
• Actually, in case of infinite diameter assuming that $p$ and $q$ both satisfy the Talagrand transportation-cost inequality, i.e $W_{d,2}(p,r)\le \sqrt{(2/\rho)\operatorname{kl}(r\|p)}$ for any distribution $r$ on $X$ relatively continuous w.r.t $p$, with a similar story for $q$ (e.g for standard Gaussian, this holds with $\rho=1$), allows us to still get an upper bound, namely $w_{d,2}(p,q) \le \sqrt{2\min (\beta\log(\beta),(1/\alpha)\log(1/\alpha))/\rho}$. – dohmatob Aug 30 '18 at 4:20
• For sure. In fact, you only need to assume that either $p$ or $q$ (not both) satisfies a log-Sobolev inequality to get this. This estimate depend on the $\rho$ in the log-Sobolev inequality, so this introduces another ingredient while eliminating the diameter. – Gabe K Aug 30 '18 at 14:20