= Total variation distance
{title2=$\lVert\mu-\nu\rVert_{\mathrm{TV}}$}
<Total variation distance> asks how much two <probability distributions> can disagree about the same <event>. For <probability measures> $P,Q$ on one <measurable space> $(S,\mathcal F)$, its definition is
$$
d_{\mathrm{TV}}(P,Q)=\lVert P-Q\rVert_{\mathrm{TV}}=\sup_{A\in\mathcal F}|P(A)-Q(A)|.
$$
The <supremum> ranges over all <measurable sets>, so $d_{\mathrm{TV}}(P,Q)\leq\varepsilon$ guarantees that every yes-or-no prediction has <probability> error at most $\varepsilon$. This <metric> takes values between zero and one; it is zero exactly when the two <probability measures> agree. This makes it useful for comparing a sampling <algorithm>'s output with its target <probability distribution>, and for defining the <mixing time of a Markov chain>.
On a <finite set>, add the excess <probability mass> wherever $P$ exceeds $Q$. That excess is also half the sum of all absolute differences:
$$
d_{\mathrm{TV}}(P,Q)=\frac12\sum_{x\in S}|P(x)-Q(x)|=1-\sum_{x\in S}\min\{P(x),Q(x)\}.
$$
The last expression reveals the common <probability mass> that the two <probability distributions> can share.<Markov Chains and Mixing Times, second edition by David A. Levin and others>[§4.1, Proposition 4.2 and Remark 4.3, printed p. 48; §4.2, equation (4.13), printed p. 51]{ref} The <coupling characterization of total variation distance> turns this overlap into an actual joint construction; <minimum sum of errors in a simple hypothesis test> gives it a statistical interpretation. One quantity connects probability bookkeeping, comparison of sampling methods, and the limits of a <statistical test>.
Back to article page
