4
$\begingroup$

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?

$\endgroup$

3 Answers 3

6
$\begingroup$

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*} $$

$\endgroup$
4
$\begingroup$

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|)$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .