Show that the total variation distance is equal to the Wasserstein distance with respect to the Hamming distance

Question

Let $(E,\mathcal E)$ be a measurable space such that $$\Delta:=\{(x,x):x\in E\}\in\mathcal E,$$ $\mu$ and $\nu$ be probability measures on $(E,\mathcal E)$, $\mathcal C(\mu,\nu)$ denote the set of couplings of $\mu$ and $\nu$ and $$\operatorname W:=\inf_{\gamma\in\mathcal C(\mu,\:\nu)}\int1_{\Delta^c}\:{\rm d}\gamma$$ denote the Wasserstein distance of $\mu$ and $\nu$ with respect to the Hamming distance $1_{\Delta^c}$. Moreover, let $$\left\|\mu-\nu\right\|:=\sup_{B\in\mathcal E}|(\mu-\nu)(B)|$$ denote the total variation distance of $\mu$ and $\nu$.

How can we show that $\operatorname W=\left\|\mu-\nu\right\|$?

Since $$(E\times B)\cap\Delta=\{(x,x):x\in B\}=(B\times E\cap\Delta\}\tag1,$$ we have $$\mu(B)-\nu(B)=\gamma((B\times E)\cap\Delta^c)-\gamma((E\times B)\cap\Delta^c)\tag2$$ for all $B\in\mathcal E$. We should be able to obtain "$\ge$" from that ...

Remark: Please come up with a proof which does not rely on considering random variables with marginal distribution $\mu$ and $\nu$.

Answer 1

As for the your first, hinted-at inequality:

Suppose $0\leq \epsilon < \|\mu-\nu\|$, is such that $B \in \mathcal E$ satisfies $\mu(B) - \nu(B) \geq \epsilon$. Then,

$$\underbrace{\gamma(B \times B^C)}_a - \underbrace{\gamma(B^C \times B)}_b = \big(\gamma(B \times B^C ) + \gamma(B\times B) \big) - \big(\gamma(B \times B) + \gamma(B^C\times B) \big)$$ $$\qquad = \gamma(B \times E) -\gamma(E \times B) = \mu(B) - \nu(B)\geq \epsilon.$$

I.e. the constants $a$ and $b$ satisfy 1) $a-b \geq \epsilon$, and 2) $a,b\geq 0$.

Since $b > 0$, this gives $a + b \geq \epsilon$; and that's sufficient:

$$ \epsilon \leq a+ b = \int_{B \times B^C \,\sqcup\,B^C\times B} \mathrm d\gamma \leq \int_{\Delta^C}\; \mathrm d \gamma$$

So taking infimum over $\gamma$ gives $W\geq \epsilon$, and taking $\epsilon \to \|\mu - \nu\|$ from below gives you the desired "$\geq$".

As for the converse inequality (this time with feeling):

By the Hahn-Jordan theorem, we can decompose into two signed measures, $$\mu - \nu = (\mu-\nu)^+ - (\mu-\nu)^-. \tag{1}$$

Denoting the measure $$\mu\cap\nu = \mu - (\mu-\nu)^+ = \nu -(\mu-\nu)^- \tag{2},$$ which we get by rearranging $(1)$, we can define a measure $\eta$ on the $\sigma$-algebra generated by $\mathcal E \times \mathcal E$ as follows:

$$\eta(A\times C) = (\mu\cap\nu)(A \cap C) + \frac{(\mu-\nu)^+(A)\, (\mu-\nu)^-(C)}{1 - (\mu\cap\nu)(E)}.$$

Now, using the fact that $$(\mu\cap\nu)(E) = 1 - (\mu\cap\nu)^+(E) = 1 - (\mu-\nu)^-(E) \tag3$$ (which is direct from $(2)$), we obtain the necessary properties for $\eta$ to be a coupling of $\mu$ and $\nu$:

• $\eta$ is a measure: since the second term is a weighted product measure, and the first term is also a measure (one supported on $\Delta$);
• $\displaystyle \eta(A \times E) = \underbrace{\vphantom{\underbrace{\frac{(\mu-\nu)^-(E)}{1 - (\mu\cap\nu)(E)}}_{=1,\text{ by }(3)}}(\mu\cap\nu)(A) + (\mu-\nu)^+(A)}_{= \mu(A),\text{ by }(3)}\underbrace{\frac{(\mu-\nu)^-(E)}{1 - (\mu\cap\nu)(E)}}_{=1,\text{ by }(3)} = \mu(A);$ and
• similarly, $\eta(E \times C) = \nu(C)$.

Furthermore, it is simple to see that $\eta(\Delta) \leq (\mu\cap\nu)(E \cap E)$ (since again, this measure is supported on $\Delta$), and so

$$W \leq 1 - \eta(\Delta) \leq 1 - (\mu\cap\nu)(E) = \|\mu - \nu\|$$

If these equalities involving $(\mu \cap \nu)(E)$ are in any doubt, they are the first mentioned in Lemma 3.1 here.