Exercise 3.13: Total Variation and Wasserstein
To begin with, we show that
\begin{equation} \TV(\P, \Q) = \sup_{f \colon \X \to [0, 1]} \int f(p - q) \isd \mu \end{equation}
where \(\mu\) is a probability measure such that \(\P = p\, \mu\) and \(\Q = q\, \mu\) and the supremum ranges over all measurable functions taking values in \([0, 1]\). Consider \(A = \set{p \ge q}\). Let \(f \colon \X \to [0, 1]\) and note that
\begin{equation} \int f (p - q) \isd \mu \le \int \ind_A (p - q) \isd \mu = \P(A) - \Q(A) \le \TV(\P, Q). \end{equation}
Therefore,
\begin{equation} \sup_{f \colon \X \to [0, 1]} \int f(p - q) \isd \mu \le \TV(\P, \Q). \end{equation}
Conversely, let \(B\) be a Borel set. Then
\begin{equation} \P(B) - \Q(B) = \int \ind_B (p - q) \isd \mu \le \sup_{f \colon \X \to [0, 1]} \int f(p - q) \isd \mu. \end{equation}
Similarly,
\begin{equation} \Q(B) - \P(B) = \int (1 - \ind_B) (q - p) \isd \mu = \int \ind_B (p - q) \isd \mu \le \sup_{f \colon \X \to [0, 1]} \int f(p - q) \isd \mu, \end{equation}
which proves the claim.
By Kantorovich–Rubinstein duality, it holds that
\begin{equation} W_\rho(\P, \Q) = \sup_{\norm{f}\lip \le 1} \int f (p - q) \isd \mu. \end{equation}
If \(\rho(x, y) = \ind(x \neq y)\), then \(\norm{f}\lip \le 1\) if and only if
\begin{equation} \abs{f(x) - f(y)} \le \ind(x \neq y) \iff f \colon \X \to [c, c + 1], \end{equation}
and observe that we may choose \(c = 0\). We conclude that
\begin{equation} W_\rho(\P, \Q) = \sup_{f \colon \X \to [0, 1]} \int f(p - q) \isd \mu \end{equation}
if \(\rho(x, y) = \ind(x \neq y)\).