I am trying to find a proof for the following inequality, but I did not get anywhere following the references from the paper I was reading. 


Consider two probability measures $P$ and $Q$ both absolutely continuous to a given measure. Then for any event $A$ we have,


\begin{align}
P(A) + Q(A^c) \geq \frac{1}{2}\exp\{-\min(\mathrm{KL}(P,Q),\mathrm{KL}(Q,P))\}
\end{align}



KL divergence Inequality
$\def\KL{\mathsf{KL}}$I'm not an expert (sorry), but it is intuitively obvious (and should follow from the standard properties) that $\KL(P,Q)$ would decrease if we replace $P$ and $Q$ by $\bar P$ and $\bar Q$ which are proportional on $A$ and $A^c$, and $\bar P(A)=P(A)$, $\bar Q(A)=Q(A)$.


If so, then the required inequality is reduced to 
$$
 p+q
 \geq \frac12\exp\left(-p\ln\frac{p}{1-q}-(1-p)\ln\frac{1-p}q\right)
 =\frac12\left(\frac{1-q}p\right)^p\left(\frac q{1-p}\right)^{1-p},
$$
where $p=P(A)$, $q=Q(A^c)$.


Now,
$$
 \left(\frac{1-q}p\right)^p\left(\frac q{1-p}\right)^{1-p}
 =\left(\sqrt{\frac{1-q}p}\right)^{2p}\left(\sqrt{\frac q{1-p}}\right)^{2(1-p)}
 \leq\left(\frac12\left(2p\cdot\sqrt{\frac{1-q}p}+2(1-p)\cdot\sqrt{\frac{q}{1-p}}\right)\right)^2
 =\left(\sqrt{p(1-q)}+\sqrt{q(1-p)}\right)^2\leq 2(p(1-q)+q(1-p))<2(p+q),
$$
as required.


