Total Variation Distance and Its Equivalent Forms

Comparing Two Distributions

Two probability distributions can differ in many ways: they may assign different probabilities to individual states, or give different probabilities to a particular collection of states. Total variation distance packages the largest such discrepancy into one number. It is useful because it has several equivalent forms: a supremum over events, a sum of differences between point probabilities, and a supremum over bounded functions. Each form highlights a different way to interpret or compute the same quantity.

Let \(S\) be a countable state space, and let \(\mu\) and \(\nu\) be probability distributions on \(S\). Thus \(\mu(i)\ge0\), \(\nu(i)\ge0\) for every \(i\in S\), and \(\sum_{i\in S}\mu(i)=\sum_{i\in S}\nu(i)=1\). For \(A\subseteq S\), write \(\mu(A)=\sum_{i\in A}\mu(i)\), with the empty sum equal to zero.

This definition asks for the event on which the two distributions disagree most. The difference \(\mu(A)-\nu(A)\) is a signed quantity: either distribution may assign the larger probability to \(A\). The absolute value makes the distance symmetric. Since event probabilities lie in \([0,1]\), this distance is at most \(1\).

Equivalent Formulas

Proof. Since \(\mu\) and \(\nu\) are probability distributions, \(\sum_{i\in S}\sigma(i)=1-1=0\). Also \(\sum_{i\in S}|\sigma(i)|\le\sum_i(\mu(i)+\nu(i))=2\), so all sums below converge absolutely. Define \(S_+=\{i:\sigma(i)>0\}\) and \(S_-=\{i:\sigma(i)<0\}\). Let \(a=\sum_{i\in S_+}\sigma(i)\) and \(b=\sum_{i\in S_-}|\sigma(i)|\). The zero total sum gives \(a-b=0\), hence \(a=b\). For any \(A\subseteq S\), \(\sigma(A)\le a\), because its positive terms sum to at most \(a\) and its negative terms can only decrease the sum. Also \(\sigma(A)\ge-b=-a\). Therefore \(|\sigma(A)|\le a\) for every \(A\). Taking \(A=S_+\) gives \(\sigma(A)=a\), so \(\sup_A|\sigma(A)|=a=b\). Finally, \(\sum_i|\sigma(i)|=a+b=2a\), proving the event and point-mass formulas, including the case \(a=0\).

For a function \(f\) with \(0\le f(i)\le1\), the sum \(\sum_i f(i)\sigma(i)\) is at most \(a\), since its positive terms are at most the positive mass \(a\) and its negative terms are nonpositive. It is at least \(-b=-a\), by the corresponding bound on its negative terms. Thus its absolute value is at most \(a\). Choosing \(f=\mathbf{1}_{S_+}\) gives the value \(a\), so the first function supremum equals \(a\). For \(|g(i)|\le1\), the triangle inequality gives \(\left|\sum_i g(i)\sigma(i)\right|\le\sum_i|\sigma(i)|=2a\). Choosing \(g(i)=1\) on \(S_+\), \(g(i)=-1\) on \(S_-\), and \(g(i)=0\) when \(\sigma(i)=0\) gives \(2a\). This proves the final formula and both function characterizations. \(\square\)

The proof also identifies an event that attains the supremum: collect exactly the states where \(\mu(i)>\nu(i)\). This set is \(S_+\). Its complement collects the states where \(\nu(i)>\mu(i)\), together with any ties, and has the opposite signed difference because \(\sigma(S)=0\). The maximizing event need not be guessed by inspecting every possible subset.

For a general finite signed measure \(\sigma\) on a countable set, its total variation mass is \(\sum_i|\sigma(i)|\). When \(\sigma=\mu-\nu\), the total mass is zero, so the supremum over events is half this mass. This distinction matters: the signed-measure total variation mass is not itself the probability-distribution distance under the convention used here; it is twice that distance.

Worked Calculations

Interpreting the Distance and Avoiding a Common Error

The event form answers a direct question: among all ways of grouping states into an event, how different can the two event probabilities be? The mass-function form answers a computational question: how much probability must be accounted for across all states where the distributions differ? The signed-measure form explains why only one side of the discrepancy is needed: because the total signed mass is zero, the positive and negative discrepancies have equal size.

A common mistake is to identify total variation distance with \(\sum_i|\mu(i)-\nu(i)|\), without dividing by two. For the first worked example, that incorrect calculation gives \(|\tfrac13|+|0|+|-\tfrac13|=\tfrac23\). But the largest event discrepancy is only \(\tfrac13\): the positive difference is \(\tfrac13\), and the negative difference has the same magnitude, so the sum of absolute differences counts both sides. Dividing by two gives the correct distance \(\tfrac13\).

Another useful check is the extreme case. If \(\mu=\nu\), every signed difference is zero, so every formula gives distance zero. If the distributions put all their mass on disjoint subsets, then the event consisting of the support of \(\mu\) has probabilities \(1\) and \(0\); the distance is \(1\), and the point-mass sum is \(2\). These checks match the range \(0\le\|\mu-\nu\|_{\mathrm{TV}}\le1\) established by the equivalent formulas.