Let $\mathcal{X}$ be the input or feature space, let $\mathcal{B}$ be Borel $\sigma$-algebra on $\mathcal{X}$ and $P(\mathcal{X})$ denotes the set of all probability measures on $(\mathcal{X},\mathcal{B})$. Let $P\_1, P\_2 \in P(\mathcal{X})$, The total variation is defined by
$$\delta(P\_1, P\_2) = \sup\_{A\in \mathcal{B}}|P\_1(A)-P\_2(A)|$$


I would like to ask for the idea of proving the following lemma,


Let $P\_1, P\_2 \in P(\mathcal{X})$ and let $\mathcal{F}$ the unit ball in $L^{\infty}(\mathcal{X})$,


$$\mathcal{F}=\{f \in L^{\infty}(\mathcal{X}) | \; ||f||\_{\infty} \leq 1\}$$
then we have the following characterization for the total varation distance
$$\delta(P\_1, P\_2) = \sup\_{f\in\mathcal{F}}|\mathbb{E}\_{x\sim P\_1}f(x) - \mathbb{E}\_{x\sim P\_2}f(x)|$$



Total variation distance
$\newcommand{\X}{\mathcal X}\newcommand{\B}{\mathcal B}\newcommand{\F}{\mathcal F}\newcommand{\De}{\Delta}\newcommand{\de}{\delta}$Let $\mu:=P\_1-P\_2$, so that $\mu$ is a finite signed measure. By the [Hahn--Jordan decomposition](https://en.wikipedia.org/wiki/Hahn_decomposition_theorem), there exist sets $\X^\pm\in\B$ such that $\X^+\cap\X^-=\emptyset$, $\X^+\cup\X^-=\X$, the functions $\mu^\pm$ defined by the formulas $\mu^+(B):=\mu(B\cap\X^+)$ and $\mu^-(B):=-\mu(B\cap\X^-)$ for $B\in\B$ are (nonnegative) measures, and
\begin{equation}
 \mu=\mu^+-\mu^-. 
\end{equation}


So, for any $f\in\F$,
\begin{equation}
\begin{aligned}
 \int\_\X f\,dP\_1-\int\_\X f\,dP\_2&=\int\_\X f\,d\mu \\ 
 &=\int\_{\X^+} f\,d\mu+\int\_{\X^-} f\,d\mu \\ 
 &=\int\_{\X^+} f\,d\mu^+ -\int\_{\X^-} f\,d\mu^- \\ 
 &\le\int\_{\X^+} 1\,d\mu^+ -\int\_{\X^-} (-1)\,d\mu^- \\ 
 &=\mu^+(\X)+\mu^-(\X). 
\end{aligned}
\end{equation}
Similarly, $\int\_\X f\,dP\_2-\int\_\X f\,dP\_1\le\mu^+(\X)+\mu^-(\X)$ and hence
\begin{equation}
 \Big|\int\_\X f\,dP\_1-\int\_\X f\,dP\_2\Big|\le\mu^+(\X)+\mu^-(\X),
\end{equation}
with the equality if $f=1\_{\X^+}-1\_{\X^-}$. So,
\begin{equation}
\begin{aligned}
\De(P\_1,P\_2)&:=\sup\_{f\in\F}|E\_{x\sim P\_1}f(x) - E\_{x\sim P\_2}f(x)| \\ 
&=\max\_{f\in\F}\Big|\int\_\X f\,dP\_1-\int\_\X f\,dP\_2\Big| \\ 
&= \mu^+(\X)+\mu^-(\X)=2\mu^+(\X);
\end{aligned}
\end{equation}
the latter equality holds because $0=P\_1(\X)-P\_2(\X)=\mu(\X)=\mu^+(\X)-\mu^-(\X)$, so that $\mu^+(\X)=\mu^-(\X)$.


On the other hand, for any $A\in\B$ we have $P\_1(A)-P\_2(A)=\mu(A)=\mu^+(A)-\mu^-(A)\le\mu^+(A)\le\mu^+(\X)$ and similarly $P\_2(A)-P\_1(A)=-\mu(A)=\mu^-(A)-\mu^+(A)\le\mu^-(A)\le\mu^-(\X)=\mu^+(\X)$, so that $|P\_1(A)-P\_2(A)|\le\mu^+(\X)$, with the equality if $A=\X^+$. So,
\begin{equation}
 \de(P\_1,P\_2)=\mu^+(\X)=\frac12\,\De(P\_1,P\_2).
\end{equation}
(You had the factor $\frac12$ missing.)




---


*Remark:* Here $\B$ does not have to be a Borel $\sigma$-algebra; it can be any $\sigma$-algebra over any set $\X$.


