= Solution
Using the paper's full-$\ell^1$ convention, the <total variation distance> is
$$
\lVert P-Q\rVert_{\rm TV}
=\sum_{a\in A}|P(a)-Q(a)|.
$$
Let $A_+=\{a:P(a)\geq Q(a)\}$. Since the signed differences sum to zero,
$$
\lVert P-Q\rVert_{\rm TV}
=2\sum_{a\in A_+}\{P(a)-Q(a)\}
=2\{P(A_+)-Q(A_+)\}.
$$
For every $B\subseteq A$, its positive difference is at most the sum over $A_+$, and its negative difference has the same bound by taking the complement. Therefore
$$
\lVert P-Q\rVert_{\rm TV}
=2\sup_{B\subseteq A}|P(B)-Q(B)|.
$$
Back to article page
