Entropy is upper bounded by cardinality of the random variable How can one prove that the entropy of random variable $X$ is upper bounded by $\log|X|$?
I tried the following $$H(x) = - \sum_x p(x)\log p(x)$$ $$ \leq - \sum_x p(x)\sum_x\log p(x)$$ $$= - \sum_x\log p(x)$$
But that doesn't get me to the proof. Does anyone know how to continue?
 A: The concavity of $\log$ and Jensen's inequality is enough to show the upper bound :
$$
\begin{align*}
H(X) &= \mathbb{E}\left(\log_2 \frac{1}{\mathbb{P}_X(X)}\right)\\
&\le \log_2 \mathbb{E} \left(\frac{1}{\mathbb{P}_X(X)}\right)\hspace{2cm}(\textrm{Jensen's inequality})\\
& = \log_2 |\mathcal{X}|.
\end{align*}
$$
A: Prove that $H(x)$ is maximum when $p(x)=1/|X|$. You can use Lagrange multipliers for example, with the constraint $\sum_x p(x)=1$. Thus,
$$H(x)\leq -\sum_x \frac{1}{|X|}\log(1/|X|)=\log(|X|)$$
A: I'd like to provide one more approach(seems simpler). 
According to the concavity of entropy, we obtain:
$H(p) = \log |\mathcal{X}|-D(p||u)$
And the minimum of $D(p||u)$ is $0$ iff $p$ follows a uniform distribution $u$(convexity of relative entropy).
$D(p||u) = \sum p(x) \log \frac{p(x)}{u(x)} \overset{\text{log sum inequality}}\ge (\sum p(x))\log \frac{\sum p(x)}{\sum u(x)}=0$.   
Then we can easily get that $H(p)\le log|\mathcal{X}|$, the equation holds iff $p$ is a uniform distribution. If you don't know the log sum inequality please refer to this.
