Hardness of Simple Hypothesis Test Through Total Variation

The TV distance encodes the hardness of simple HT. Intuitively, a simple HT tries to distinguish between two distributions $P_{{\theta }_1}$ and $P_{{\theta }_0}$ that possibly generate the sample data. And the TV distance measures their distinguishability.

Formally, consider an unbiased Bayes risk:

$$R_B(A,\mathrm{Unif})=\frac{1}{2}\left(\int A(x)\mathrm{d}{P}_0(x)+\int (1-A(x))\mathrm{d}{P}_1(x)\right),$$

where we consider a randomized test $A:\mathcal{X}\to [0,1]$ such that $A(X)$ is the probability of rejecting null. Note that this risk recovers the deterministic test when $A(x)\in \{0,1\}$. Denote $S_{P_0,P_1}(A)=2R_B(A,\mathrm{Unif})$. Then, we have

Thm

$$\underset{A:\mathcal{X}\to \{0,1\}}{\inf }{S}_{P_0,P_1}(A)=1-\mathrm{TV}(P_0,P_1).$$

Proof

We know the Bayes Optimal Test is $A^{\ast }(x)=1\{p_1(x)>p_0(x)\}$. Obviously, this is also optimal for random tests. This gives the minimum Bayes risk

$$\begin{array}{rl}2R_B(A^{\ast },\mathrm{Unif})=& \int A^{\ast }(x)\mathrm{d}{P}_0(x)+\int (1-A^{\ast }(x))\mathrm{d}{P}_1(x)\\ =& 1-\int A^{\ast }(x)(p_1(x)-p_0(x))\mathrm{d}x\\ =& 1-{\int }_{p_1>p_0}(p_1(x)-p_0(x))\mathrm{d}x\\ =& 1-\mathrm{TV}(P_0,P_1).\end{array}$$