# Proof that $H(X) \leq \log(|A|)$ (Shannon entropy)

The full question states:

"Show that $$H(X) \leq \log(|A|)$$ with equality if and only if $$P_X$$ is uniform. Hint: use the Gibbs or log-sum inequality "

I used "$$A$$" as the alphabet in here. My lecturer is using curly "X" which I don't know how to type in MathJax.

The equality part is rather straight forward.

Suppose $$A=\{1,...,m\}$$ and $$P_X(x)=\frac{1}{m} \forall x$$. Then of course $$|A|=m$$ And $$H(X)=-\sum_{x=1}^m \frac{1}{m}\log(\frac{1}{m})=-\log(\frac{1}{m})=\log(m)=\log(|A|)$$

It is the inequality part that I am not sure how to show. Thanks for any help

For any probability distributions $$p, q$$ on $$A$$, Gibbs inequality states that $$H(p)=-\sum_{k\in A} p(k)\log p(k)\leq -\sum_{k\in A} p(k)\log q(k)$$ with equality iff $$p=q$$. Take $$q$$ to correspond to a uniform distribution on $$A$$. Then $$H(p)\leq -\sum_{k\in A} p(k)\log \frac{1}{|A|}=\log|A|$$ with equality iff $$p$$ is a uniform distribution as desired.
Let $$p_i$$s be the corresponding probabilities of the source $$X$$ and $$q_i={1\over |A|}$$ for $$i=1,2,\cdots , |A|$$ . Therefore using Gibbs' inequality we obtain:$$H(X)=-\sum p_i\log p_i\le -\sum p_i\log q_i=-\log {1\over |A|}\sum p_i=\log |A|$$