The Exercise

A classical experiment has a finite set $X$ of outcomes, and two probability distributions $p$ and $q$ on it give the outcome $x$ the probabilities $p_x$ and $q_x$ . An event is a subset $S$ of $X$ , and its probability under $p$ is the sum $p(S) = \sum_{x \in S} p_x$ of the probabilities of its outcomes; $q(S)$ is the same sum for $q$ . The exercise is to show that the trace distance between the two distributions is the largest amount by which a single event can be more likely under $p$ than under $q$ : the maximum of the signed difference $p(S) - q(S)$ over all events $S$ .^✦

The Trace Distance

For two real functions $p$ and $q$ on a finite set $X$ , the classical trace distance $D(p,q)$ is the real number equal to half the sum, over all points of $X$ , of the absolute differences of their values: $D(p,q) = \frac{1}{2} \sum_{x \in X} \lvert p_x - q_x \rvert .$ (1)^✦ For two probability distributions $p$ and $q$ on $X$ , the classical trace distance $D(p,q)$ is the trace distance of the exercise.

The Claim

Theorem 1. Let $p$ and $q$ be real functions on a finite set $X$ with the same total, $\sum_{x} p_x = \sum_{x} q_x$ . Then $D(p,q) = \max_{S \subseteq X} \bigl( p(S) - q(S) \bigr) .$ (2)^✦

Theorem 2. Let $p$ and $q$ be real functions on $X$ that each have total one, $\sum_{x} p_x = 1$ and $\sum_{x} q_x = 1$ . Then $D(p,q) = \max_{S \subseteq X} \bigl( p(S) - q(S) \bigr) .$ (3)^✦

Two probability distributions on $X$ satisfy both hypotheses, and either theorem is then the exercise.

What Is Checked

The claim is stated over the classical trace distance (1) of two real functions on a finite set, set against their totals $p(S)$ and $q(S)$ over every subset.