Binary Testing Error and Total Variation

Why Testing Errors Measure Distinguishability

Suppose an observation comes from one of two possible distributions, and we must decide which one generated it. If the distributions are well separated, a test can often make both kinds of mistake rare. If they overlap substantially, no decision rule can avoid errors on observations that are plausible under both possibilities. Total variation distance quantifies this limitation exactly: it determines the smallest possible sum of the two testing errors.

The result concerns testing two fixed distributions, also called two simple hypotheses. It does not require a parametric model or a particular form of the observation. We work on a measurable space \((\mathcal X,\mathcal A)\), with probability measures \(P_0\) and \(P_1\). The hypotheses are \(H_0: X\sim P_0\) and \(H_1: X\sim P_1\).

Tests, Errors, and Total Variation

A nonrandomized test chooses one hypothesis for each observation. A randomized test is described by a measurable function \(\phi:\mathcal X\to[0,1]\), where \(\phi(x)\) is the probability of choosing \(H_1\) after observing \(x\). Thus, \(\phi(x)=1\) means always choose \(H_1\), while \(\phi(x)=0\) means always choose \(H_0\). Nonrandomized tests are the special case where \(\phi\) only takes values zero and one.

We use the convention \(\|P_1-P_0\|_{\mathrm{TV}}=\sup_{A\in\mathcal A}|P_1(A)-P_0(A)|\). For probability measures this is also the largest signed difference \(P_1(A)-P_0(A)\), since replacing \(A\) by its complement reverses the sign. If \(\mu\) is any measure dominating both distributions, with densities \(p_0\) and \(p_1\), then \(\|P_1-P_0\|_{\mathrm{TV}}=\frac12\int |p_1-p_0|\,d\mu\). The factor of one half is part of this convention.

The density expression follows because \(\int(p_1-p_0)\,d\mu=1-1=0\). The positive and negative parts of \(p_1-p_0\) therefore have equal integrals. Each integral is half the integral of the absolute difference; the positive-part integral is also the largest possible value of \(P_1(A)-P_0(A)\), obtained by taking \(A=\{x:p_1(x)>p_0(x)\}\). We can always use \(\mu=P_0+P_1\), so such densities exist even when the distributions do not have densities with respect to counting or Lebesgue measure.

The Exact Minimum Sum of Errors

Proof. Let \(\mu=P_0+P_1\), and let \(p_0\) and \(p_1\) be the densities of \(P_0\) and \(P_1\) with respect to \(\mu\). For any test \(\phi\), the definitions give

Since \(0\leq\phi\leq1\), the integral being subtracted cannot exceed the integral of the positive part of \(p_1-p_0\):

The last equality follows from the positive-part identity for total variation given above. Consequently, every test satisfies \(\alpha(\phi)+\beta(\phi)\geq1-\|P_1-P_0\|_{\mathrm{TV}}\). Now take \(\phi^*(x)=1\) when \(p_1(x)>p_0(x)\), and \(\phi^*(x)=0\) otherwise. This is measurable, and \(\int\phi^*(p_1-p_0)\,d\mu=\int(p_1-p_0)_+\,d\mu=\|P_1-P_0\|_{\mathrm{TV}}\). Substitution into the error-sum identity attains the lower bound. On the tie set, where \(p_1=p_0\), any value of \(\phi\) contributes zero to the integral and leaves the sum unchanged. This proves the result. \(\square\)

Continuous Distributions and Overlap

When both distributions have densities with respect to Lebesgue measure, the same theorem says that the optimal test chooses \(H_1\) where \(p_1(x)>p_0(x)\). The total variation distance is half the integrated absolute density difference. Equivalently, for probability densities, it is one minus the integral of their pointwise minimum. Indeed, \(\min(p_0,p_1)=\frac12(p_0+p_1-|p_1-p_0|)\); integrating gives \(1-\|P_1-P_0\|_{\mathrm{TV}}\). Thus the minimum error sum is exactly the mass of the shared density overlap.

Interpreting the Result Carefully

The theorem gives a direct operational meaning to total variation: it is the greatest reduction in the sum of testing errors below one that any test can achieve. If \(P_0=P_1\), the distance is zero and the minimum sum is one; observing \(X\) gives no information for distinguishing the hypotheses. If the distributions are mutually singular, their total variation distance is one and a test can have both errors equal to zero. Intermediate values describe intermediate distinguishability.

The result concerns the sum of the two errors. If the two hypotheses instead have equal prior probabilities, the average error probability of a test is \((\alpha+\beta)/2\). Therefore the minimum average error under equal priors is \((1-\|P_1-P_0\|_{\mathrm{TV}})/2\). This factor of two matters when moving between conventions.

Common mistake: confusing total variation with the full \(L^1\) distance. From densities, a reader may calculate \(\int|p_1-p_0|\,d\mu\) and call it total variation, then conclude the minimum error sum is one minus that quantity. Under the convention used here, total variation is half the \(L^1\) distance. For the Bernoulli example, the \(L^1\) distance is \(1\), while total variation is \(1/2\), and the minimum error sum is \(1-1/2=1/2\), not zero. Always check whether a source defines total variation with or without the factor of one half.

The density-comparison test also has a clear interpretation: choose the hypothesis that assigns greater density or mass to the observed outcome. This is not a claim that the test makes both error probabilities individually as small as possible; changing decisions can trade type I error against type II error. The theorem identifies the minimum of their sum, which is the quantity exactly characterized by total variation.