Proving maximal entropy [closed]

Question

It is quite easy to prove that

$$H(S) \leq \log_2(|A|),$$

where $A$ is the number of events, using the Jensen inequality

$$H(S) = E_S[\log_2(\frac{1}{P_S(s)})]\leq \log_2(E_S[(\frac{1}{P_S(s)})]) = \log_2(\sum_{s\in A}1 ) = \log_2(|A|).$$

I tried to prove it using the logarithmic inequality

$$\log_2(x) \leq (x-1)\log_2(e)$$

$$H(S) = E_S[\log_2(\frac{1}{P_S(s)})] \leq E_S[(\frac{1}{P_S(s)}-1)]\log_2(e)\leq \log_2(e)[E_S(\frac{1}{P_S(s)})-1].$$

But I am not sure how to conclude that it is less than the required value.

I will appreciate if someone has any clue. Thanks

Answer 1

The problem above is that you are not applying the inequality $$\log _2(x) \leq (x-1)\log _2(e)$$ where it is most effective, namely around $x = 1$. You can get what you want by rescaling. Taking $y_s = \frac{1}{|A|P_S(s)}$ we have ${\mathbb E}_S(y_s) = 1$. Applying the logarithmic inequality to $y_s$ then gives \begin{equation*} H(S) - \log |A| = {\mathbb E}_S[ \log _2 ( y_s ) ] \leq {\mathbb E}_S[(y_s - 1)] \log _2 (e) = 0. \end{equation*}