Total variation norm of probability measures related to $L_1$-norm?

Question

On Wikipedia the following is stated:

I don't see how, if the set is countable, $$ \delta (P, Q) = \sup_{A \in \mathcal{F}} \vert P(A) - Q(A)\vert = \frac{1}{2} \vert \vert P- Q\vert \vert _1$$ holds. Can someone explain that identity?

Answer 1

Intuitively, consider the set $G=\{x | P(x) \geq Q(x)\}$. If you wanted to put together a set $A$ to maximize $P(A)-Q(A)$, you couldn't do better than including all the points $x\in G$ where $P(x)-Q(x)\geq 0$ while excluding all the points $x\not\in G$ where $P(x)-Q(x)\leq 0$, right? So, the supremum of $P(A)-Q(A)$ is achieved at $A=G$. By a symmetrical argument, the supremum of $Q(A)-P(A)$ is achieved at $A=G^c$. Therefore, the supremum of $|P(A)-Q(A)|$ is achieved at either $G$ or $G^c$.

What's less obvious is that this supremum is achieved at both $G$ and $G^c$. That's because $P$ and $Q$ are both probability measures, so: $$P(G)-Q(G) = (1-P(G^c))-(1-Q(G^c)) = Q(G^c)-P(G^c)$$ and either one of these is equal to $$\delta(P,Q) = \sup|P(A)-Q(A)|=P(G)-Q(G)=Q(G^c)-P(G^c)$$

Now, consider the $L_1$ norm: $$\|P-Q\|_1=\sum_x |P(x)-Q(x)| = \sum_{x\in G}(P(x)-Q(x)) + \sum_{x\in G^c}(Q(x)-P(x))$$ As we established above, both terms on the right-hand side are equal to $\delta(P,Q)$, so: $$\|P-Q\|_1 = 2\delta(P,Q)$$