Total variation between two measures Let $p_0, p_1$ be two densities with corresponding measures $P_0, P_1$ such that $d_{TV} (P_0, P_1) > 0$. Define set of measures $B = \left \{ P : d_{TV}(P, P_1) \leq \frac{d_{TV}(P_0, P_1)}{2} \right\}$. I want to prove that $\int_{p_1 > p_0} (p - p_0) \geq \frac{d_{TV}(P_0, P_1)}{2}$ where is p is a density corresponding to $P\in B$.
So far, I have tried decomposing the set $\{p_1 > p_0\}$ to write out the integral but have not gotten anywhere.
Any hint would be appreciated.
 A: Lemma 1: $\int\limits_{p_0 > p_1} (p_1 - p_0) = \int\limits_{p_1 > p_0} (p_0 - p_1).$
Proof. Since $p_0$ and $p_1$ integrate to one on $\mathbf{R}^d,$ we see
$$
0 = \int\limits_{\mathbf{R}^d} (p_1-p_0) = \int\limits_{p_1 - p_0 \neq 0}(p_1 - p_0)
$$
and the result follows since $\{p_1 - p_0 \neq 0\} = \{p_1 > p_0\} \cup \{p_0 > p_1\}.$ Q.E.D.
Lemma 2: $d_{\mathrm{TV}}(P_0, P_1) = \int\limits_{p_1 > p_0} (p_1-p_0).$
Proof. If we show that any Borel set $A$ satisfies
$$
\int\limits_{p_1 > p_0} (p_0 - p_1) \leq P_1(A) - P_0(A) \leq \int\limits_{p_1 > p_0} (p_1 - p_0)
$$
then $d_{\mathrm{TV}}(P_0, P_1) \leq \int\limits_{p_1 > p_0} (p_1 - p_0)$ and the equality would follow by taking the Borel set $A = \{p_1 > p_0\}.$ Thus, suffices to show the aforementioned condition. Now, if $A$ is any Borel set,
$$
P_1(A) - P_0(A) = \int\limits_A (p_1 - p_0) = \int\limits_{A \cap \{p_1 > p_0\}} (p_1 - p_0) + \int\limits_{A \cap \{p_0 > p_1\}} (p_1 - p_0) \leq \int\limits_{p_1 > p_0} (p_1 - p_0)
$$
since, on the set $A \cap \{p_1 > p_0\} \subset \{p_1 > p_0\}$ the integrand is positive and on $A \cap \{p_1 < p_0\}$ the integrand is negative. For the reverse inequality, we show similarly
$$
P_1(A) - P_0(A) = \int\limits_{A \cap \{p_0 > p_1\}} (p_1 - p_0) \geq \int\limits_{p_0 > p_1} (p_1 - p_0) = \int\limits_{p_1 > p_0} (p_0 - p_1)
$$
where intequality follows from the negativity of the integrand on the region of integration and the last equality follows form lemma 1. Q.E.D.
Proof of the exercise. Write
$$
\int\limits_{p_1 > p_0} (p - p_0) = \int\limits_{p_1 > p_0} (p - p_1 + p_1 - p_0) = \int\limits_{p_1 > p_0} (p - p_1) + d_{\mathrm{TV}}(P_0, P_1)
$$
by lemma 2. Clearly, $\int\limits_{p_1 > p_0} (p - p_1) \geq -d_{\mathrm{TV}}(P, P_1) \geq -\dfrac{d_{\mathrm{TV}}(P_0, P_1)}{2}.$ The desired result follows at once. Q.E.D.
