Commmon Problems of Entropy

Common problems of Shannon entropy in information theory.

Theorem: Deterministic Distribution Minimizes The Entropy

What is the minimum value of $H(p_1,\dots ,p_n)=H(\mathbf{p})$ as $\mathbf{p}$ ranges over the set of $n$-dimensional probability vectors? Find all p's which achieve this minimum.

Solution: We wish to find all probability vectors $\mathbf{p}=(p_1,\dots ,p_n)$ which minimize $$H(\mathbf{p})=-\sum _i{p}_i\log p_i.$$

Now $-p_i\log p_i\ge 0$, with equality iff $p_i=0$ or 1 . Besides we know that $\sum _i{p}_i=1$.

Hence the only possible probability vectors which minimize $H(\mathbf{p})$ are those with $p_i=1$ for some $i$ and $p_j=0,j\ne i$. There are $n$ such vectors, i.e., $(1,0,\dots ,0),(0,1,0,\dots ,0),\dots ,(0,\dots ,0,1)$, and the minimum value of $H(\mathbf{p})$ is 0 .

Theorem: Uniform Distribution Maximizes The Entropy

Source:

1. Why is Entropy maximised when the probability distribution is uniform?
2. Why does $\log (1+x)=x+O(x^2)$ when $𝑥\to 0$?

Proof

Heuristically, the probability density function on $\{x_1,x_2,\dots ,x_n\}$ with maximum entropy turns out to be the one that corresponds to the least amount of knowledge of $\{x_1,x_2,\dots ,x_n\}$, in other words the Uniform distribution.

Now, for a more formal proof consider the following: A probability density function on $\{x_1,x_2,\dots ,.x_n\}$ is a set of nonnegative real numbers $p_1,\dots ,p_n$ that add up to 1 . Entropy is a continuous function of the $n$-tuples $(p_1,\dots ,p_n)$, and these points lie in a compact subset of ${\mathbb{R}}^n$, so there is an $n$-tuple where entropy is maximized. We want to show this occurs at $(1/n,\dots ,1/n)$ and nowhere else.

Suppose the $p_j$ are not all equal, say $p_1<p_2$. (Clearly $n\ne 1$.) We will find a new probability density with higher entropy. It then follows, since entropy is maximized at some $n$-tuple, that entropy is uniquely maximized at the $n$-tuple with $p_i=1/n$ for all $i$.

Since $p_1<p_2$, for small positive $\epsilon$ we have $p_1+\epsilon <p_2-\epsilon$. The entropy of $\{p_1+\epsilon ,p_2-\epsilon ,p_3,\dots ,p_n\}$ minus the entropy of $\{p_1,p_2,p_3,\dots ,p_n\}$ equals $$-p_1\log \left(\frac{p_1+\epsilon }{p_1}\right)-\epsilon \log (p_1+\epsilon )-p_2\log \left(\frac{p_2-\epsilon }{p_2}\right)+\epsilon \log (p_2-\epsilon )$$

To complete the proof, we want to show this is positive for small enough $\epsilon$. Rewrite the above equation as $$\begin{array}{rl}-p_1\log (1+\frac{\epsilon }{p_1})& -\epsilon (\log p_1+\log (1+\frac{\epsilon }{p_1}))-p_2\log (1-\frac{\epsilon }{p_2})\\ & +\epsilon (\log p_2+\log (1-\frac{\epsilon }{p_2}))\end{array}$$

Recalling that $\log (1+x)=x+O\left(x^2\right)$ for small $x$, the above equation is $$-\epsilon -\epsilon \log p_1+\epsilon +\epsilon \log p_2+O\left({\epsilon }^2\right)=\epsilon \log \left(p_2/p_1\right)+O\left({\epsilon }^2\right)$$ which is positive when $\epsilon$ is small enough since $p_1<p_2$.

Simpler Proof

Recalling that $H(X)\le \log |\mathcal{X}|$ with equality if and only has a uniform distribution over $\mathcal{X}$.

Then for any r.v. $X$, it's maximum entropy is $\log |\mathcal{X}|$, and is achieved by a uniform distribution over $\mathcal{X}$.

Drawing with and without replacement

Drawing with and without replacement. An urn contains $r$ red, $w$ white, and $b$ black balls. Which has higher entropy, drawing $n\ge 2$ balls from the urn with replacement or without replacement?

Solution:

Let random variable $X_i$ denotes the outcome color of the $i-$th ball. The alphabate of all $X_i$ is the same: $\mathcal{X}=\{0,1,2\}$, where

1. $X_i=0$ if the ball is red,
2. $X_i=1$ if the ball is white
3. $X_i=2$ if the ball is black.

Let $p_{X_i}$ denote the PMF of $X_i$.

For the case with replacement:

For all $X_i\in X_1,\cdots ,X_n$, Since the total number of red, white, black balls are $r,w,b$, $$p(X_i)=\{\begin{array}{ll}\frac{r}{r+w+b}& \text{if }X=1\\ \frac{w}{r+w+b}& \text{if }X=2\\ \frac{b}{r+w+b}& \text{if }X=3.\end{array}$$ $p(X_i)$ doesn't change during the drawing process, so all $p(X_i)$ are independant(because of the replacement).

Due to Theorem: Entropy is additive for independent r.v., $$H(X_1,X_2,\cdots ,X_k)=H\left(X_1\right)+H\left(X_2\right)+\cdots +H\left(X_k\right).$$ For the case without replacement:

the picks are not independent anymore, due to the chain rule for joint entropy, we have $$\begin{array}{rl}H(X_1,X_2,\cdots ,X_k)& =H\left(X_1\right)+H(X_2\mid X_1)+\cdots +H(X_k\mid X_1,\cdots ,X_k-1).\end{array}$$

Meanwhile, due to Theorem: Theorem: Conditioning reduces entropy, we have: $$H\left(X_1\right)+H(X_2\mid X_1)+\cdots +H(X_k\mid X_1,\cdots ,X_k-1)\le H\left(X_1\right)+H\left(X_2\right)+\cdots +H\left(X_k\right)$$ Hence, the sample with replacement has higher entropy.