Total Variation Distance

Mathematical Definition

For two probability distributions P and Q defined over a finite sample space Ω, the total variation distance is defined as:

TV(P, Q) = 1/2 ∑_{ω ∈ Ω} |P(ω) - Q(ω)|

An equivalent definition interprets TV distance as the maximum possible difference in probabilities assigned to the same subset (event) A ⊆ Ω:

TV(P, Q) = max_{A ⊆ Ω} |P(A) - Q(A)|

The event A that achieves this maximum is known as the positive witness event, consisting of all outcomes where P assigns a strictly greater probability than Q.

Worked example: The witness event

Consider the sample space {0, 1, 2} and two distributions:

• P = (0.5, 0.3, 0.2)
• Q = (0.2, 0.5, 0.3)

We first calculate the element-wise absolute differences:

1. For outcome 0: |0.5 - 0.2| = 0.3
2. For outcome 1: |0.3 - 0.5| = 0.2
3. For outcome 2: |0.2 - 0.3| = 0.1

The sum of these absolute differences is 0.3 + 0.2 + 0.1 = 0.6. The total variation distance is half of this sum, so TV = 0.3.

The witness event consists of all outcomes i where P_i > Q_i. Here, only outcome 0 satisfies this (0.5 > 0.2), so the witness event is {0}. The difference in probability assigned to this event is exactly |P({0}) - Q({0})| = |0.5 - 0.2| = 0.3, matching the TV.

Maximal Couplings

A coupling of P and Q is a joint distribution on Ω × Ω such that its marginals are exactly P and Q. A maximal coupling is one that maximizes the probability that the two random variables are equal (i.e., the sum of the diagonal elements of the joint distribution matrix).

Coupling inequality guarantees that for any coupling (X, Y):

P(X ≠ Y) ≥ TV(P, Q)

A maximal coupling achieves equality here, meaning the maximum probability of equality is exactly 1 - TV(P, Q).

Reproduce the calculation in the module

Open the Total Variation Distance experiment to explore how TV and maximal couplings change as distributions are mixed.

1. Set Distribution pair to Default and Mix t to 1.0. You'll see the base vectors P = (0.5, 0.3, 0.2) and Q_mixed = Q = (0.2, 0.5, 0.3). Observe the TV is 0.300000, and the witness event is {0}.
2. Adjust Mix t to 0.5. The distribution Q_mixed interpolates halfway toward P, becoming (0.35, 0.40, 0.25). The TV distance halves to 0.150000, illustrating the linearity of TV distance under convex combinations.
3. Change the Distribution pair to Disjoint and set Mix t to 1.0. Notice that P and Q_mixed share no overlapping mass. The TV distance becomes its maximum possible value of 1.000000, and the maximal coupling joint has all zero mass on the diagonal.
4. Change the Distribution pair to Identical. The TV distance drops to exactly 0.000000, and the positive witness event becomes the empty set ∅.

What the diagram cannot establish

The visualizations compute TV and the specific maximal coupling purely over discrete categorical events of a small dimension (size 3). Real-world applications often involve continuous state spaces (requiring integrals rather than sums) or massive discrete state spaces (like card shuffling permutations) where explicit iteration over all states and subsets is computationally intractable.

Additionally, while the calculated maximal coupling is theoretically optimal, in practice, probability theorists often construct non-maximal couplings (like path-coupling in Markov chains) simply to upper-bound the TV distance without knowing the exact optimal joint distribution.

Sources

Stanford CS265: Randomized Algorithms and Probabilistic Analysis (Lecture 15) formally introduces total variation distance, the coupling lemma, and their applications to analyzing the mixing time of Markov chains.