Proving a reverse of Pinsker's inequality

621 Views Asked by At

Let $P$ and $Q$ be probability distributions on the finite set $A$. Let $A_+ = \{a : Q(a) > 0\}$ and let $\alpha_Q = \mathrm{min}_{a∈A_+} Q(a)$.

How to prove that if $D(P||Q) < \infty$ then $$D(P||Q) \leq \frac{d^2(P,Q)}{\alpha_q \cdot \mathrm{ln}2},$$ where $d(P, Q)$ is the variational distance of distributions $P$ and $Q$, i.e., $d(P, Q) = \sum_{a\in A}|P(a) − Q(a)|$.

I was given a hint that first should prove that: $$D(P||Q) \leq \sum_{a\in A_+} \frac{P(a)}{\mathrm{ln}2}(\frac{P(a)}{Q(a)}-1) = \frac{1}{\mathrm{ln}2}\sum_{a\in A_+}\frac{|P(a)-Q(a)|^2}{Q(a)}.$$

1

There are 1 best solutions below

0
On

For the Hint from the right hand side to the middle is easy, hint distract the squared expression. $$ \sum_{a\in A_+}\frac{P(a)}{\mathrm{ln2}}(\frac{P(a)}{Q(a)}-1) = \frac{1}{\mathrm{ln}2} \sum_{a\in A_+}P(a)exp(ln \frac{P(a)}{Q(a)})-1 \geqslant \frac{1}{\mathrm{ln}2}exp(\sum_{a\in A_+}P(a)ln(\frac{P(a)}{Q(a)})) -1\\ \geqslant exp(D(P||Q)) -1\\ \geqslant 1+D(P||Q) - 1 = D(P||Q)$$

For the reversed pinker's; $$ D(P||Q) \leqslant \frac{1}{\mathrm{ln}2}\sum_{a\in A_+}\frac{|P(a)-Q(a)|^2}{Q(a)}\\ \leqslant \frac{1}{\mathrm{ln}2}\sum_{a\in A_+}\frac{|P(a)-Q(a)|^2}{min_{a\in A_+}Q(a)} \leqslant \frac {max_{a\in A_+}|P(a)-Q(a)|. \sum_{a\in A_+} |P(a)-Q(a)|}{\alpha_Q . ln2} \leqslant \frac {d^2(P,Q)}{\alpha_Q . ln2} $$

The last inequality you can deduce it after using scheffe's theorem for variational distance.