[proofplan] A measurable test $\phi$ is equivalent to its rejection region $A_\phi=\phi^{-1}(\{1\})$. We rewrite the testing risk in terms of this measurable set and reduce the infimum over tests to an infimum over measurable subsets of $\mathcal X$. The remaining point is that maximizing the signed difference $Q(A)-P(A)$ gives exactly the total variation distance, because complements reverse the sign of $P(A)-Q(A)$ for probability measures. [/proofplan]

[step:Replace each measurable test by its rejection region]Let $\mathcal T$ denote the set of measurable maps \begin{align*} \phi:(\mathcal X,\mathcal A) \to (\{0,1\},\mathcal P(\{0,1\})). \end{align*} For $\phi \in \mathcal T$, define its rejection region $A_\phi \in \mathcal A$ by \begin{align*} A_\phi := \phi^{-1}(\{1\}). \end{align*} Then $\{\phi=1\}=A_\phi$ and $\{\phi=0\}=\mathcal X \setminus A_\phi$, so \begin{align*} P(\phi=1)+Q(\phi=0)=P(A_\phi)+Q(\mathcal X\setminus A_\phi). \end{align*} Since $Q$ is a probability measure, $Q(\mathcal X)=1$, and finite additivity gives $Q(\mathcal X\setminus A_\phi)=1-Q(A_\phi)$. Therefore \begin{align*} P(\phi=1)+Q(\phi=0)=1-\bigl(Q(A_\phi)-P(A_\phi)\bigr). \end{align*} Conversely, for every $A \in \mathcal A$, let $\mathbb{1}_A:\mathcal X\to\{0,1\}$ denote the indicator function of $A$, defined by $\mathbb{1}_A(x)=1$ for $x\in A$ and $\mathbb{1}_A(x)=0$ for $x\in\mathcal X\setminus A$. Define the indicator test $\phi_A:(\mathcal X,\mathcal A)\to(\{0,1\},\mathcal P(\{0,1\}))$ by $\phi_A(x):=\mathbb{1}_A(x)$ for $x\in\mathcal X$. Since $A \in \mathcal A$, the map $\phi_A$ is measurable, and its rejection region is $A$. Therefore the set of risks obtained by measurable tests is exactly \begin{align*} \left\{1-\bigl(Q(A)-P(A)\bigr): A \in \mathcal A\right\}. \end{align*} Hence \begin{align*} \inf_{\phi \in \mathcal T}\{P(\phi=1)+Q(\phi=0)\} =1-\sup_{A \in \mathcal A}\bigl(Q(A)-P(A)\bigr). \end{align*}[/step]

[guided]A test $\phi$ only matters through the set on which it outputs $1$. We therefore define, for a measurable test \begin{align*} \phi:(\mathcal X,\mathcal A) \to (\{0,1\},\mathcal P(\{0,1\})), \end{align*} the measurable set \begin{align*} A_\phi := \phi^{-1}(\{1\}). \end{align*} This set is measurable because $\phi$ is measurable and $\{1\}\in \mathcal P(\{0,1\})$. Since $\phi$ only takes the values $0$ and $1$, we also have \begin{align*} \{\phi=0\}=\mathcal X \setminus A_\phi. \end{align*} Using that $Q$ is a probability measure, so $Q(\mathcal X)=1$, and using finite additivity on the disjoint union $\mathcal X=A_\phi\cup(\mathcal X\setminus A_\phi)$, we compute \begin{align*} P(\phi=1)+Q(\phi=0)=P(A_\phi)+Q(\mathcal X\setminus A_\phi). \end{align*} Also $Q(\mathcal X\setminus A_\phi)=Q(\mathcal X)-Q(A_\phi)=1-Q(A_\phi)$, so \begin{align*} P(\phi=1)+Q(\phi=0)=1-\bigl(Q(A_\phi)-P(A_\phi)\bigr). \end{align*} This shows that every test gives a risk determined by one measurable set. We also need the converse: every measurable set must come from some test. Given $A \in \mathcal A$, let $\mathbb{1}_A:\mathcal X\to\{0,1\}$ denote the indicator function of $A$, defined by $\mathbb{1}_A(x)=1$ for $x\in A$ and $\mathbb{1}_A(x)=0$ for $x\in\mathcal X\setminus A$. Define $\phi_A:(\mathcal X,\mathcal A)\to(\{0,1\},\mathcal P(\{0,1\}))$ by $\phi_A(x):=\mathbb{1}_A(x)$ for $x\in\mathcal X$. The map $\phi_A$ is measurable because $\phi_A^{-1}(\{1\})=A\in\mathcal A$ and $\phi_A^{-1}(\{0\})=\mathcal X\setminus A\in\mathcal A$. Its rejection region is exactly $A$. Thus minimizing over tests is the same as minimizing over measurable rejection regions: \begin{align*} \inf_{\phi \in \mathcal T}\{P(\phi=1)+Q(\phi=0)\}=\inf_{A \in \mathcal A}\left\{1-\bigl(Q(A)-P(A)\bigr)\right\}. \end{align*} The elementary order identity $\inf_A(1-r_A)=1-\sup_A r_A$, applied to the [real numbers](/page/Real%20Numbers) $r_A:=Q(A)-P(A)$, gives \begin{align*} \inf_{\phi \in \mathcal T}\{P(\phi=1)+Q(\phi=0)\}=1-\sup_{A \in \mathcal A}\bigl(Q(A)-P(A)\bigr). \end{align*}[/guided]

[step:Identify the signed supremum with total variation] Define \begin{align*} S:=\sup_{A \in \mathcal A}\bigl(Q(A)-P(A)\bigr). \end{align*} For every $A \in \mathcal A$, \begin{align*} P(A)-Q(A) &=Q(\mathcal X\setminus A)-P(\mathcal X\setminus A), \end{align*} because $P(\mathcal X)=Q(\mathcal X)=1$. Since $\mathcal X\setminus A \in \mathcal A$, this gives \begin{align*} P(A)-Q(A)\le S. \end{align*} Also $Q(A)-P(A)\le S$ by definition of $S$. Hence \begin{align*} |P(A)-Q(A)|\le S \end{align*} for every $A \in \mathcal A$, and therefore \begin{align*} \operatorname{TV}(P,Q)\le S. \end{align*} The reverse inequality follows from \begin{align*} Q(A)-P(A)\le |P(A)-Q(A)|\le \operatorname{TV}(P,Q) \end{align*} for every $A \in \mathcal A$. Taking the supremum over $A$ gives \begin{align*} S\le \operatorname{TV}(P,Q). \end{align*} Thus \begin{align*} \sup_{A \in \mathcal A}\bigl(Q(A)-P(A)\bigr)=\operatorname{TV}(P,Q). \end{align*} [/step]

[step:Substitute the total variation identity into the risk formula] Combining the reduction to rejection regions with the identity from the previous step gives \begin{align*} \inf_{\phi \in \mathcal T}\{P(\phi=1)+Q(\phi=0)\}=1-\sup_{A \in \mathcal A}\bigl(Q(A)-P(A)\bigr). \end{align*} Since $\sup_{A \in \mathcal A}\bigl(Q(A)-P(A)\bigr)=\operatorname{TV}(P,Q)$, we obtain \begin{align*} \inf_{\phi \in \mathcal T}\{P(\phi=1)+Q(\phi=0)\}=1-\operatorname{TV}(P,Q). \end{align*} This is the desired formula. [/step]