Exercise 3.1: Shannon Entropy and Kullback–Leibler Divergence

chapter 3

(a)

Let \(U\) be uniformly distributed over \(\X\) and set \(Z = p(U)\). Then

\begin{equation} \E[Z] = \sum_{x \in \X} \frac{1}{\abs{\X}} p(x) = \frac1{\abs{\X}}, \quad \E[Z \log Z] = \sum_{x \in \X} \frac{1}{\abs{\X}} p(x) \log p(x) = -\frac1{\abs{\X}} H(\X). \end{equation}

Therefore,

\begin{equation} \Hb(Z) = \E[Z \log Z] - \E[Z] \log \E[Z] = \frac{1}{\abs{\X}}(\log\,\abs{\X} - H(\X)). \end{equation}

(b)

From \(\Hb(Z) \ge 0\) it follows that \(H(\X) \le \log\,\abs{\X}\), and \(\log\,\abs{\X} = H(U)\).

(c)

Set \begin{equation} Y = \frac{p(X)}{q(X)}, \quad X \sim q. \end{equation} Then \(\E[Y] = 1\), so \(\Hb(Y) = \E[Y \log Y] = \KL(p, q)\).