Back to the on-screen lesson · Print

Bounds on entropy

The bounds $0 \le H \le \log_2 n$, the distributions that attain each end, and why a function of $X$ never carries more entropy than $X$.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to prove that entropy lies between $0$ and $\log_2$ of the number of outcomes, say exactly which distributions attain each end, explain why a function of a random variable never has more entropy than the variable itself, sort statements about entropy into the ones that always hold and the ones that do not, and use these bounds to check any entropy you compute.

2. What you already have

Entropy as average surprise, exact for dyadic distributions, and the binary entropy function with its peak at the fair coin. This lesson asks how large and how small an entropy can be at all, and which distributions sit at the ends.

3. Support, uniform, function of a variable

The support of a distribution is the set of outcomes with positive probability, and $n$ counts them. The uniform distribution gives each of them $1/n$. A function of $X$, $Y = f(X)$, merges outcomes of $X$ that share a value of $f$. Gibbs' inequality, $D(p \| q) \ge 0$, is quoted here and proved two lessons on.

4. How large and how small entropy can be

Every term $p \log_2 (1/p)$ is nonnegative, so $H(X) \ge 0$, and $H(X) = 0$ exactly when one outcome has probability $1$. At the other end, $H(X) \le \log_2 |\mathcal{X}|$ with equality only for the uniform distribution: the proof compares $p$ with the uniform $u$ through Gibbs' inequality $D(p \| u) \ge 0$, which unfolds to $\log_2 n - H(X) \ge 0$. Two further facts follow the same pattern. A function of $X$ has no more entropy than $X$: $H(f(X)) \le H(X)$, with equality when $f$ is injective on the support, because merging outcomes can only make the variable more predictable. And relabelling outcomes changes nothing, since $H$ depends only on the multiset of probabilities. These bounds are the sanity checks for every computation in the course: a result outside $[0, \log_2 n]$ is wrong.

5. The proof of $H(X) \le \log_2 n$, line by line

Let $p$ be any distribution on $n$ outcomes and $u(x) = 1/n$ the uniform one. Gibbs' inequality (proved in lesson 4 from Jensen) says $D(p \| u) \ge 0$. Expand the divergence: $$D(p \| u) = \sum_x p(x) \log_2 \frac{p(x)}{1/n} = \sum_x p(x) \log_2 p(x) + \sum_x p(x) \log_2 n = -H(X) + \log_2 n.$$ So $\log_2 n - H(X) \ge 0$, and the gap between the maximum and the actual entropy is exactly $D(p \| u)$. Equality in Gibbs needs $p = u$, so only the uniform distribution reaches $\log_2 n$. The lower bound is easier: every term $p \log_2 (1/p)$ is $\ge 0$, and the sum is $0$ only when each term is, which forces every $p(x)$ to be $0$ or $1$: a single certain outcome.

Read the table downwards: as the bars flatten, the entropy climbs toward $\log_2 3$ and the gap shrinks to $0$. The gap is never negative.

6. Functions of a random variable

Why can $Y = f(X)$ never have more entropy than $X$? Use the chain rule (lesson 3) on the pair $(X, Y)$ twice. Since $Y$ is determined by $X$, $H(Y \mid X) = 0$ and $H(X, Y) = H(X) + H(Y \mid X) = H(X)$. But also $H(X, Y) = H(Y) + H(X \mid Y) \ge H(Y)$. Hence $H(Y) \le H(X)$, with equality exactly when $H(X \mid Y) = 0$, that is when $X$ can be recovered from $Y$: $f$ is injective on the outcomes that actually occur. The lost amount $H(X \mid Y) = H(X) - H(f(X))$ is how much of $X$ the function threw away.

The pattern in the last row is the one the practice uses: when $X$ is uniform on $2^{j + m}$ values, $X \bmod 2^j$ is uniform on $2^j$ residues (each residue is hit by exactly $2^m$ values), so $H(Y) = j$ bits and the function discarded $m$ bits. By contrast $Y = X^2$ on positive values is injective, so $H(X^2) = H(X)$: squaring loses nothing.

7. Solving the practice problems

1. Largest entropy with $2^k$ values: $\log_2 2^k = k$ bits. With $n$ values: $\log_2 n$ from the log table, to three decimals ($n = 6$ gives $2.585$).
2. $Y = X \bmod 2^j$ for $X$ uniform on $2^{j + m}$ values: $Y$ is uniform on $2^j$ values, so $H(Y) = j$. Do not confuse the modulus with the answer: the answer is its logarithm.
3. Which statement is always true: the safe statements are $0 \le H(X) \le \log_2 n$, equality at $0$ only for a certain outcome, equality at $\log_2 n$ only for the uniform distribution. Anything claiming $H(X) \le n$, $H(X) = \log_2 n$ for every $X$, or a dependence on the values of $X$ is false.

Common mistakes

• Writing $n$ instead of $\log_2 n$ for the maximum: ten values allow $3.322$ bits, not $10$.
• Thinking a spread of large numbers has more entropy than a spread of small ones: only the probabilities matter.
• Answering $H(Y) = H(X)$ for $Y = X \bmod m$: the residue forgets the quotient, and $H(Y)$ is only $\log_2 m$ when $X$ is uniform on a multiple of $m$ values.

8. Where this usually goes wrong

The commonest slip is writing $n$ instead of $\log_2 n$ for the maximum: ten values allow $3.322$ bits, not $10$. The second is believing a spread of large numbers has more entropy than a spread of small ones; only the probabilities matter, and relabelling changes nothing. The third is answering $H(Y) = H(X)$ for $Y = X \bmod m$: the residue forgets the quotient, and $H(Y)$ is $\log_2 m$ only when $X$ is uniform on a multiple of $m$ values. And the equality cases are sharp: $H = \log_2 n$ needs the uniform distribution, not merely a spread-out one.

9. Proving $H(X) \le \log_2 n$

1. Let $u$ be uniform on the $n$ outcomes. Gibbs: $D(p \| u) = \sum p \log_2 \dfrac{p}{1/n} \ge 0$.

   Relative entropy against the uniform.

2. Expand: $\sum p \log_2 p + \sum p \log_2 n = -H(X) + \log_2 n \ge 0$.

   $\sum p = 1$ pulls $\log_2 n$ out.

3. So $H(X) \le \log_2 n$, with equality only when $p = u$.

   Gibbs is tight only at equality of the distributions.

10. Entropy of a function

1. $X$ uniform on $\{1, \ldots, 8\}$, $H(X) = 3$; $Y = X \bmod 2$ takes two values, each from four $X$ values, so $Y$ is a fair bit.

   Compute the distribution of $Y$.

2. $H(Y) = 1 \le 3 = H(X)$: merging outcomes lost two bits.

   $H(f(X)) \le H(X)$.

11. The bound for six outcomes

1. Six outcomes allow at most $\log_2 6 = 2.585$ bits.

   $\log_2 6 = \log_2 2 + \log_2 3 = 1 + 1.585$.

2. The distribution $(0.5, 0.1, 0.1, 0.1, 0.1, 0.1)$ has $H = 0.5 \cdot 1 + 5 \cdot 0.1 \cdot 3.322 = 0.5 + 1.661 = 2.161$ bits.

3. $2.161 \le 2.585$ as it must be; the gap $0.424$ is $D(p \| u)$.

12. Entropy of $X \bmod 4$ for $X$ uniform on $\{1, \ldots, 32\}$

1. $H(X) = \log_2 32 = 5$ bits.

2. Each residue $0, 1, 2, 3$ is hit by exactly $8$ of the $32$ values, so $Y$ is uniform on $4$ values and $H(Y) = 2$ bits.

   Uniform in, uniform out, because $4$ divides $32$.

3. The function discarded $H(X \mid Y) = 5 - 2 = 3$ bits: the quotient, which takes $8$ equally likely values.

13. Your turn: can a distribution on $5$ outcomes have entropy $2.5$ bits?

1. The maximum is $\log_2 5 \approx 2.322$ bits.

2. Your turn: work this step out. Its working is at the end of the packet.

   $2.5 > 2.322$: no such distribution exists.

14. Guided practice

A random variable takes $4$ values. Give the set of values its entropy $H$, in bits, can possibly take, as an interval.

This task has no paper form; do it on a device.

15. Guided practice

Build the proof that a random variable with $n$ values has $H(X) \le \log_2 n$, with equality only for the uniform distribution.

This task has no paper form; do it on a device.

16. Practice

$X$ is uniform on $\{1, 2, \ldots, 32\}$ and $Y = X \bmod 2$. Fill in how many values $Y$ takes, and the entropies of $Y$ and of $X$, in bits.

17. Practice

$X$ takes $6$ values. Select every statement that is true for every distribution of $X$.

This task has no paper form; do it on a device.

18. Somewhere new

A hash table has $16$ buckets and a key is drawn uniformly from $128$ possible keys; the hash sends exactly $8$ keys to each bucket. What is the entropy, in bits, of the bucket the key lands in?

Answer:

19. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

20. Test question

Sort each distribution by where its entropy sits: at zero, at the maximum $\log_2 n$ for its number of values, or strictly between.

21. What you can do now

You can bound entropy, name the extreme distributions, and say how much a function of a variable forgets. Say in your own words why the uniform distribution is the only one at the top of the range, and what a certain outcome does to the bottom. Next: Jensen's inequality, the convexity tool behind every entropy inequality.

Working for the steps left to you

13. Your turn: can a distribution on $5$ outcomes have entropy $2.5$ bits?, step 2