Consider two distributions $P(·)$ and $Q(·)$ on the alphabet ...

Question

Consider two distributions $P(·)$ and $Q(·)$ on the alphabet $\chi = \{a_1 , a_2 ... , a_k \}$ such that $Q(a_i) \gt 0 $ show that:

$\sum_{i = 1}^n \frac{P(a_i)^2}{Q(a_i)} \ge 1 $

Answer 1

Taking the expectation under the $P$-measure:

$$ \sum_{i=1}^n \frac {P(a_i)^2} {Q(a_i)} = E\left[\frac {P(A)} {Q(A)}\right] = E\left[\left(\frac {Q(A)} {P(A)}\right)^{-1}\right] \geq E\left[\frac {Q(A)} {P(A)}\right]^{-1} = \sum_{i=1}^n \frac {Q(a_i)} {P(a_i)} P(a_i) = 1 $$

where the inequality follows from Jensen's inequality. WLOG the inverse operation is valid as we can assume all $P(a_i) > 0$; if not we just simply discard the term as we are taken expectation under the $P$-measure.