L1 norm of difference between two probability distributions over a finite set Let $P$ and $Q$ be two probability distributions over a finite set $\mathcal{A} = \lbrace 1,2,\dots, a\rbrace$,
show that
$\|Q-P\|_1 = 2 \max_{A \in \mathcal{A}} (Q(A) - P(A))$,
where $\|Q-P\|_1 = \sum_{k=1}^{a} |Q(k) - P(k)|$
Could someone provide a proof of this identity? Does it go by a certain name? I found it in this publicly available  paper (equation 14).
 A: It is often referred to as Scheffé's identity, but essentially it boils down to applying the definition of total variation distance to the event $A \stackrel{\rm def}{=}\{k : Q(k)>P(k)\}$. Then
$$
\|Q-P\|_1 = 2(Q(A)-P(A)) \tag{1}
$$
To see why, note that adding any element to $A$ will reduce the RHS (since, if $k$ is any such element, then
$$
Q(A\cup \{k\})-P(A\cup\{k\}) = Q(A)-P(A) + \underbrace{Q(k)-P(k)}_{\leq 0}
$$
as $k\notin A$). Similarly, removing any element from $A$ can only reduce the RHS. So we have (1).
But we have $Q(A)-P(A) = P(A^c)-Q(A^c)$ (can you see why?), and so
$$
\|Q-P\|_1 (Q(A)-P(A)) + (P(A^c)-Q(A^c))\tag{2}
$$
Now, this gives what we want, since $$
Q(A)-P(A) = \sum_{k\in A} |Q(k)-P(k)|, \; P(A^c)-Q(A^c) = \sum_{k\notin A} |Q(k)-P(k)|\tag{3}
$$
(as the absolute values are "just for show:" by definition of $A$ and $A^c$, $Q(k)>P(k)$ for all $k\in A$, and $Q(k)\leq P(k)$ for all $k\notin A$). This shows that
$$
\|Q-P\|_1 = \sum_{k=1}^a |Q(k)-P(k)|\,.\tag{4}
$$
as claimed.
A: This is Scheffé's lemma [1]:
For mutually continuous measures $\mu, \nu$ with densities $f,g$ respectively we have:
$$1 = \int_Afdx + \int_{A^c} fdx$$
so we have:
$$\int_A f - g dx = \int_{A^c} g - f dx$$
Letting $A$ be the set over which $f > g$ then:
$$\int \left | f - g \right | dx = 2\int_A f - g dx = 2 \left | \mu(A) - \nu(A) \right |$$
Finally notice that the RHS attains its supremal value for $A$ as defined: those values for which $f > g$.
References
[1] Scheffé, Henry. "A useful convergence theorem for probability distributions." The Annals of Mathematical Statistics 18.3 (1947): 434-438.
