[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*}
[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]
[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]
