Total Variation Distance

Why This Matters

Total variation distance is the cleanest notion of worst-case distributional discrepancy. If you give two models the freedom to disagree on any measurable event, total variation asks: what is the biggest probability gap they can produce?

That single quantity shows up everywhere:

• in coupling arguments, where TV is the disagreement probability under the best joint construction
• in KL divergence, via Pinsker's inequality
• in Wasserstein distance, as the contrast case where geometry is ignored
• in MCMC and mixing-time theory, where convergence is often stated directly in TV

Mental Model

Three equivalent readings are worth holding at once:

1. Overlap view. Remove the shared mass $\min(p,q)$; what remains is TV.
2. Event view. Let an adversary pick the measurable set $A$ where the two distributions disagree most. The biggest gap $|P(A)-Q(A)|$ is TV.
3. Coupling view. Draw $X \sim P$ and $Y \sim Q$ on the same probability space in the smartest possible way. The smallest possible probability that $X \neq Y$ is TV.

Each view is mathematically equivalent, but each teaches a different instinct.

Core Definitions

Definition

Total Variation Distance$\mathrm{TV}(P,Q)$

For two probability measures $P$ and $Q$ on the same measurable space,

$\mathrm{TV}(P,Q) := \sup_{A} |P(A)-Q(A)|.$

The supremum runs over all measurable sets $A$.

When densities $p$ and $q$ exist with respect to a common dominating measure, this becomes

$\mathrm{TV}(P,Q) = \frac12 \int |p(x)-q(x)|\,dx = 1-\int \min(p,q)\,dx.$

So TV is literally half the $L^1$ distance, or equivalently one minus the overlap mass.

Main Theorems

Theorem

Equivalent Forms of Total Variation

Statement

The following are equivalent:

$\mathrm{TV}(P,Q)=\sup_A |P(A)-Q(A)|=\frac12\int |p-q|\,dx=1-\int \min(p,q)\,dx.$

If $p$ and $q$ are densities, the extremizing event is

$A^*=\{x: p(x)>q(x)\}.$

Intuition

The signed difference $p-q$ has positive and negative regions. If you want the biggest possible probability gap, you keep exactly the region where $p$ exceeds $q$ and ignore the region where it falls below. That converts the absolute-value integral into the measurable-event supremum.

Proof Sketch

Split the space into $A^*=\{p>q\}$ and its complement. On $A^*$, the difference $p-q$ is positive; on the complement, it is negative. Therefore

$\int |p-q|\,dx = \int_{A^*}(p-q)\,dx + \int_{(A^*)^c}(q-p)\,dx = 2(P(A^*)-Q(A^*)).$

This gives $\mathrm{TV}(P,Q)=P(A^*)-Q(A^*)=\tfrac12\int|p-q|\,dx$. The overlap identity follows from the pointwise equality $|p-q|=p+q-2\min(p,q)$ and the fact that $\int p=\int q=1$.

Why It Matters

This theorem is why TV is so interpretable. It is simultaneously an adversarial event gap, a density-overlap deficit, and an $L^1$ discrepancy. Different subfields pick different forms, but they are all the same object.

Failure Mode

TV ignores geometry. Two point masses at nearby locations can have $\mathrm{TV}=1$ even if the ambient metric says they are extremely close. That is exactly why Wasserstein distance exists.

Theorem

Coupling Characterization of Total Variation

Statement

Among all couplings $(X,Y)$ with marginals $P$ and $Q$,

$\mathrm{TV}(P,Q)=\inf_{(X,Y)} \mathbb P[X\neq Y].$

Moreover, there exists a maximal coupling attaining equality.

Intuition

The common overlap mass can be coupled to agree exactly. Only the leftover unmatched mass must disagree. So the best possible disagreement probability is precisely the amount of unmatched mass, which is TV.

Proof Sketch

Write the shared mass as $\mu(dx)=\min(p(x),q(x))\,dx$. Sample from the normalized overlap $\mu/\mu(\Omega)$ and set $X=Y$ there. The remaining residual masses of $P$ and $Q$ are then sampled independently on the non-overlap part. Agreement happens exactly on the shared-mass component, whose total weight is $\int \min(p,q)\,dx = 1-\mathrm{TV}(P,Q)$. Hence the disagreement probability is $\mathrm{TV}(P,Q)$.

Why It Matters

This is the bridge from abstract probability metrics to concrete stochastic processes. In mixing-time proofs, you often build a coupling and show the two chains have met by time $t$ with high probability; the theorem converts that meeting event directly into a TV bound.

Failure Mode

Not every naive coupling is maximal. A bad coupling can make the disagreement probability much larger than TV. The theorem says TV is the best possible disagreement rate, not the rate produced by an arbitrary coupling.

Pinsker's Inequality

TV and KL are linked by the classical bound

$\mathrm{TV}(P,Q)\le \sqrt{\frac12 D_{\mathrm{KL}}(P\|Q)}.$

This is useful in lower bounds, concentration arguments, and asymptotic statistics because KL often tensorizes more easily than TV. But it is only a one-way control: small KL implies small TV, while the reverse is false without extra assumptions.

Why TV and Wasserstein Feel Different

TV is a support-sensitive metric: if two distributions place mass on disjoint sets, TV is already maximal. Wasserstein is a geometry-sensitive metric: if those disjoint sets are close in the ambient space, Wasserstein can still be small.

This difference explains the common dichotomy:

• TV is natural for hypothesis testing, coupling, and mixing.
• Wasserstein is natural for transport, generative modeling, and robustness with geometric structure.

Common Confusions

Watch Out

TV is a metric, but it is not geometric

TV satisfies symmetry and the triangle inequality, so it is a genuine metric. But it does not know about ambient distances between outcomes. It only sees how much mass fails to overlap.

Watch Out

The factor 1/2 is convention, not substance

Some ML papers define TV as $\|P-Q\|_1$ without the $\frac12$. Probability texts almost always include the $\frac12$, giving range $[0,1]$. The two conventions differ by exactly a factor of two. Always check which one a paper uses before comparing constants.

Summary

• $\mathrm{TV}(P,Q)=\sup_A |P(A)-Q(A)|$
• with densities, $\mathrm{TV}(P,Q)=\frac12\int |p-q|\,dx = 1-\int \min(p,q)\,dx$
• TV is the smallest disagreement probability over all couplings
• TV is sensitive to support mismatch but blind to geometry
• Pinsker links TV to KL: $\mathrm{TV}\le \sqrt{D_{\mathrm{KL}}/2}$

Exercise

ExerciseCore

Problem

Let $P=\mathrm{Bernoulli}(0.7)$ and $Q=\mathrm{Bernoulli}(0.4)$. Compute $\mathrm{TV}(P,Q)$ using both the event-gap definition and the $\frac12\|p-q\|_1$ formula.

Hint

Reveal Solution

References

Canonical:

• Levin, Peres, and Wilmer, Markov Chains and Mixing Times (2009), Chapter 4
• Villani, Optimal Transport: Old and New (2009), Chapter 6 for the contrast with Wasserstein

Current / standard texts:

• Durrett, Probability: Theory and Examples (5th ed., 2019), sections on coupling and total variation
• van der Vaart, Asymptotic Statistics (1998), Appendix and Chapter 7 for TV-KL relations