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}
$\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.
