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.

  • $\begingroup$ Thanks, this makes sense. The standard property that you mention should follow from Jensen's. $\endgroup$
    – rajatsen91
    Sep 16 '15 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.