= Total variation distance and hypothesis testing
{title2=$\text{optimal success probability}=\tfrac12(1+d_{\mathrm{TV}}(P,Q))$}
Suppose one observation comes from either $P$ or $Q$, each with prior <probability> $1/2$. A <decision rule> that chooses $P$ on an <event> $E$ and $Q$ otherwise has success <probability>
$$
\frac12P(E)+\frac12Q(E^c)=\frac12\bigl(1+P(E)-Q(E)\bigr).
$$
On a <finite set>, choosing $E=\{x:P(x)>Q(x)\}$ therefore gives $\tfrac12(1+d_{\mathrm{TV}}(P,Q))$. This is the equal-prior version of <minimum sum of errors in a simple hypothesis test>; allowing a <statistical test> to use an auxiliary <random variable> cannot improve it, because for each outcome the better of the two decisions already maximizes its contribution.
For the four-outcome example, choose $P$ after $A$ and $Q$ after $B$ or $C$, with either decision allowed after $D$. Choosing $Q$ after $D$ yields $\tfrac12(0.4+0.9)=0.65$. \b[The best success probability is 65%, with a 35% error probability.] A smaller <total variation distance> means the two sources are harder to distinguish from one observation. Unequal prior <probabilities>, unequal costs, or multiple observations change this particular decision problem; the $65\%$ figure is not a universal bound for every experiment.
Back to article page
