# Comparison between $L^1$ Wasserstein distance and total variation distance

Wasserstein$$-k$$ distance between two probability measures $$\mu,\nu$$ on $$\mathbb{R}^d$$ is defined as:

$$W_k(\mu,\nu)=\left(\inf_{(X,Y)\in\mathcal{C}(\mu,\nu)}\mathbb{E}\left[\|X-Y \|^k \right]\right)^{1/k}$$

where $$\mathcal{C}(\mu,\nu)$$ is the set of all couplings of $$\mu,\nu$$.

Total variation distance between the same probability measures is defined as:

$$\|\mu-\nu\|_{\rm{TV}}=\max_{A\subset \mathbb{R}^d}|\mu(A)-\nu(A)|=\inf \{\mathbb{P}(X\neq Y): (X,Y)\,\text{is a coupling of \mu and \nu.}\}$$

where the $$\inf$$ is again over all couplings of $$\mu,\nu$$.

I am trying to check if the total variation distance is smaller than Wasserstein-$$1$$ distance for any two probability measures.

$$\|\mu-\nu\|_{\rm{TV}}\leq \mathbb{P}(X\neq Y)$$

where $$(X,Y)$$ is any coupling and then I was trying to apply Markov's inequality but did not succeed. Any ideas?

• A sketch of a counterexample: Consider $S_n=\sum_{i=1}^n X_i$ for $X_i$, $i=1,...,n$ i.i.d. with $\mathbb{P}(X_i=1)=\mathbb{P}(X_i=-1)=1/2$. Let $Z \sim \mathcal{N}(0,1)$. Then $\|\frac{S_n}{\sqrt{n}}-Z\|_{TV}=1$ for all $n$ (because $S_n$ is a discrete random variable), but $\mathcal{W}(S_n/\sqrt{n},Z)\rightarrow 0$ for $n \rightarrow \infty$. If it is too sketchy, I will write it down properly as an answer. Commented Mar 9, 2022 at 15:02

As @lukanz mentioned, what you are trying to prove is not true. Here is an even simpler counterexample: consider the sequence $$\delta_{\frac{1}{n}}$$ (Dirac measures centred at $$1/n$$). It is easy to check that \begin{align} \lVert\delta_0 -\delta_{1/n} \rVert_{\mathrm{TV}}=1\, , \quad \forall \, n \geq 1 \, . \end{align} On the other hand, choosing the coupling $$(X,X+1/n)$$ where $$X\sim \delta_0$$, one has that \begin{align} W_1\left(\delta_0,\delta_{\frac1n}\right) \leq \frac1n\, . \end{align} So your inequality cannot hold true. The inequality the other way does hold true but with a constant and using a weighted version of the total variation distance. You can find the statement and proof in Chapter 6 of Villani's book Optimal Transport: Old and New.
• Just to confirm, you are considering $d=1$ in $\mathbb{R}^d$, right?
• Edit (latex typo): Yes. But you can tweak the example to work in any dimension by centering the measures at $(1/n,0,\dots,0)$ in higher dimensions. Commented Mar 10, 2022 at 5:29