0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$
  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.

$\endgroup$
1
  • $\begingroup$ Thank you again! $\endgroup$ Feb 25, 2020 at 14:14

You must log in to answer this question.

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