= Solution
Put $q_i=\min(p_i,1-p_i)$. Applying part (b) after possibly replacing $X_i$ by $1-X_i$ gives $H(X_i)\leq2\sqrt{q_i}+q_i$. If $q_i<\delta_i$, then, because $0<\delta_i<1$, this is less than $3\sqrt{\delta_i}$, contradicting the assumption. Thus $p_i,1-p_i\geq\delta_i$.
The centered variables
$$
Y_i=\log P_i(X_i)+H(X_i)
$$
are independent and have mean zero. Their two possible values differ by
$$
\left|\log\frac{p_i}{1-p_i}\right|
\leq|\log\delta_i|.
$$
Applying <Hoeffding inequality> to $\sum_iY_i$ gives
$$
\mathbb P\left(\log P(X_1,\ldots,X_n)+H(X_1,\ldots,X_n)\leq-t\right)
\leq\exp\left(-\frac{2t^2}{\sum_i(\log\delta_i)^2}\right).
$$
Back to article page
