Total Variation Distance

The total variation (TV) distance is a way of quantifying the distance between probability distributions. Suppose $p(x), q(x)$ are two probability mass functions with support on set $X$. Then the total variation distance is:

$$TV(p, q) \equiv ||p - q|| := \frac{1}{2} \sum_{x \in X} |p(x) - q(x)| = max_{A \subseteq X} p(A) - q(A)$$

Properties

• Let $J$ be a joint distribution over $X, Y$, where $p$ is the marginal distribution over $X$ and $q$ is the marginal distribution over $Y$. Then

$$||p - q|| \leq \mathbb{P}[X \neq Y]$$

Furthermore, $\exists J^*$ such that this is an equality.

Proof: Let $A$ be the subset of