# Jensen's inequality and LOTUS applied to entropy in probability

I am given an example and proof for entropy:

(Entropy). The surprise of learning that an event with probability $$p$$ happened is defined as $$\log_2(1/p)$$, measured in a unit called bits. Low-probability events have high surprise, while an event with probability $$1$$ has zero surprise. The $$\log$$ is there so that if we observe two independent events $$A$$ and $$B$$, the total surprise is the same as the surprise from observing $$A \cap B$$. The $$\log$$ is base $$2$$ so that if we learn that an event with probability $$1/2$$ happened, the surprise is $$1$$, which corresponds to having received $$1$$ bit of information.

Let $$X$$ be a discrete r.v. whose distinct possible values are $$a_1, a_2, \dots, a_n$$, with probabilities $$p_1, p_2, \dots, p_n$$ respectively (so $$p_1 + p_2 + \dots + p_n = 1$$). The entropy of $$X$$ is defined to be the average surprise of learning the value of $$X$$:

$$H(X) = \sum_{j = 1}^n p_j \log_2 (1/p_j).$$

Note that the entropy of $$X$$ depends only on the probabilities $$p_j$$, not on the values $$a_j$$. So for example, $$H(X^3) = H(X)$$, since $$X^3$$ has distinct possible values $$a_1^3, a_2^3, \dots, a_n^3$$, with probabilities $$p_1, p_2, \dots, p_n$$ -- the same list of $$p_j$$'s as for $$X$$

Using Jensen's inequality, show that the maximum possible entropy for $$X$$ is when its distribution is uniform over $$a_1, a_2, \dots, a_n$$, i.e., $$p_j = 1/n$$ for all $$j$$. This makes sense intuitively, since learning the value of $$X$$ conveys the most information on average when $$X$$ is equally likely to take any of its values, and the least possible information if $$X$$ is a constant.

Solution:

Let $$X \sim \text{DUnif}(a_1, \dots, a_n)$$, so that

$$H(X) = \sum_{j = 1}^n \dfrac{1}{n} \log_2 (n) = \log_2 (n).$$

Let $$Y$$ be an r.v. that takes on values $$1/p_1, \dots, 1/p_n$$ with probabilities $$p_1, \dots, p_n,$$ respectively (with the natural modification if the $$1/p_j$$ have some repeated values, e.g., if $$1/p_1 = 1/p_2$$ but none of the others are this value, then it gets $$p_1 + p_2 = 2p_1$$ as its probability). Then $$H(Y) = E(\log_2(Y))$$ by LOTUS, and $$E(Y) = n$$. So by Jensen's inequality,

$$H(Y) = E(\log_2(Y)) \le \log_2(E(Y)) = \log_2(n) = H(X).$$

Since the entropy of an r.v. depends only on the probabilities $$p_j$$ and not on the specific values that the r.v. takes on, the entropy of $$Y$$ is unchanged if we alter the support from $$1/p_1, \dots, 1/p_n$$ to $$a_1, \dots, a_n$$. Therefore $$X$$, which is uniform on $$a_1, \dots, a_n$$, has entropy at least as large as that of any other r.v. with support $$a_1, \dots, a_n$$.

There are a couple of points that I am having difficulty understanding:

1. I don't understanding why $$H(Y) = E(\log_2(Y))$$ by LOTUS. LOTUS says that $${E}[g(X)]=\sum _{x}g(x)f_{X}(x)$$, where $$f_X(x)$$ is the probability mass function. However, it's not clear to me here what $$g(x)$$ and $$f_X(x)$$ are, and why they were chosen to be that. Would someone please explain this?

2. In the last part, it says that $$X$$ has entropy at least as large as that of any other r.v. with support $$a_1, \dots, a_n$$. But we just used Jensen's inequality to show that the maximum possible entropy for $$X$$ is when its distribution is uniform over $$a_1, a_2, \dots, a_n$$, i.e., $$p_j = 1/n$$ for all $$j$$. Since this is the maximum entropy, It seems to me that this would mean that $$X$$ has entropy at most as large as any other r.v. with support $$a_1, \dots, a_n$$, no?

Thank you.

1. Let $$P$$ be the distribution of $$Y,$$ i.e. $$P(Y=\frac{1}{p_i}) = p_i.$$ Using the definition of entropy, the definition of $$Y$$ and the definition of expectation respectively, we have \begin{align} H(Y) &= \sum_{i=1}^n p_i \log \frac{1}{p_i} \\ &= \sum_{i=1}^n P(Y = \frac{1}{p_i}) \log \frac{1}{p_i} \\ &= E(\log(Y)). \end{align} So $$g = \log,$$ and $$f_X$$ is $$P.$$
2. Not sure I understand the question. We show that any distribution has entropy at most that of a uniform distribution. As $$X$$ is uniformly distributed, it achieves this maximum entropy and any other random variable has equal or lower entropy.