Equivalency of two definitions for statistical distance

Question

Suppose X and Y are two distributions on finite discrete sample space S and we define statistical distance as fallow : $$\Delta(X,Y)=1/2 * \sum_{w\in S} |Pr(X=w)-Pr(Y=w)|$$ and i wanna proof the upper definition is equivalent to : $$sup_{A\subseteq S}|Pr(X\in A) - Pr(Y\in A)|$$

Answer 1

Define $S_+ = \{w\in S:Pr(X=w)-Pr(Y=w)>0\}$ and $S_- = S_+^c$.

Note that $\sum_{w\in S_+} Pr(X=w) = 1-\sum_{w\in S_-} Pr(X=w)$ and similarly for $Pr(Y=w)$.

Also: for $w\in S_+, |Pr(X=w)-Pr(Y=w)| =Pr(X=w)-Pr(Y=w) $; for $w\in S_-, |Pr(X=w)-Pr(Y=w)| =-Pr(X=w)+Pr(Y=w) $

Putting all the above together, we can show $$ \Delta(X,Y)=\sum_{w\in S_+} (Pr(X=w)-Pr(Y=w))$$

Now consider $d(A) = |Pr(X\in A) - Pr(Y\in A)|$:

$$d(S_+) = \sum_{w\in S_+} (Pr(X=w)-Pr(Y=w))$$ $$d(S_-) = -\sum_{w\in S_-} (Pr(X=w)-Pr(Y=w))$$ But because $\sum_{w\in S_+} Pr(X=w) = 1-\sum_{w\in S_-} Pr(X=w)$, then $d(S_+) = d(S_-)$ and more importantly $d(S_+) = \Delta(X,Y)$.

Therefore, all that remains to prove is that for any $A\subseteq S$, $d(A) \le d(S_+)$ which will then imply that $sup_{A\subseteq S}[d(A)] = d(S_+) = \Delta(X,Y)$ which is the required result.

To establish $d(A) \le d(S_+)$, consider what happens to $d(A)$ if $A \subseteq S_+$ and you remove or add another element of $S_+$. You can show $d(A)$ will only increase if you add elements of $S_+$, so this shows $S_+$ maximises $d(A)$. If you start adding elements of $S_-$ then $d(A)$ decreases.