Exercise 15.1: Alternative Representation of Total Variation Norm
From Exercise 3.13, we know that \begin{equation} \TV(\P, \Q) = \sup_{f\colon\X\to[0,1]} \int f(p - q) \isd \mu \end{equation} where $\mu$ is any probability measure such that $\P = p \mu$ and $\Q = q \mu$, e.g. $\mu = \tfrac12(\P + \Q)$, and the supremum ranges over all measure functions taking values in $[0, 1]$. We show that \begin{equation} \TV(\P, \Q) = 1 - \inf_{f_1 + f_2 = 1} \int (f_1 p + f_2 q) \isd \mu \end{equation} where the supremum ranges over all pairs $(f_1, f_2)$ where $f_1,f_2 \colon \X \to [0, \infty)$ are measurable functions. Note that we can equivalently consider the constraint $f_1 + f_2 \ge 1$. By the constraint $f_1 + f_2 = 1$, $f_1 \in [0, 1]$ and $f_2 = 1 - f_1$ is determined by $f_1$, so the pairs $(f_1, f_2)$ such that $f_1 + f_2 = 1$ are in bijection to all functions $f\colon\X \to [0, 1]$. Therefore, \begin{align} 1 - \inf_{f_1 + f_2 = 1} \int (f_1 p + f_2 q) \isd \mu &= 1 - \inf_{f\colon\X\to[0,1]} \int ((1 - f) p + f q) \isd \mu \newline &= \sup_{f\colon\X\to[0,1]} \int f (p - q) \isd \mu. \end{align}