GATE 2022 EC Q.29: solution and answer

GATE 2022 · ECQ.29 · 1 mark · MSQ

Let $H (X)$ denote the entropy of a discrete random variable $X$ taking $K$ possible distinct real values. Which of the following statements is/are necessarily true?

(A)
$H (X) \leq lo g_{2} K$ bits
(B)
$H (X) \leq H (2 X)$
(C)
$H (X) \leq H (X^{2})$
(D)
$H (X) \leq H (2^{X})$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The necessarily true statements are (A), (B) and (D).

Official answer: A, B, DSource: Official answer key, GATE 2022 EC (IIT Kharagpur)

Entropy depends only on the probability masses $p_{1}, \dots, p_{K}$ of $X$ , not on the values it takes. If $g$ is one-to-one on the values of $X$ , then $g (X)$ has the same set of masses, so $H (g (X)) = H (X)$ . If $g$ is many-to-one, some values merge and their masses add, so $H (g (X)) \leq H (X)$ .
(A) By Jensen's inequality for the concave function $lo g_{2}$ : $H (X) = \sum_{i} p_{i} lo g_{2} \frac{1}{p _{i}} \leq lo g_{2} (\sum_{i} p_{i} \cdot \frac{1}{p _{i}}) = lo g_{2} K$ , with equality for the uniform distribution. So $H (X) \leq lo g_{2} K$ bits always. True.
(B) $Y = 2 X$ is one-to-one on the real line, so the masses are unchanged and $H (2 X) = H (X)$ . Hence $H (X) \leq H (2 X)$ holds (with equality). True.
(C) $Y = X^{2}$ is many-to-one when $X$ takes both $a$ and $- a$ . Take $X \in {- 1, + 1}$ with probability $\frac{1}{2}$ each: $H (X) = 1$ bit, but $X^{2} = 1$ with certainty, so $H (X^{2}) = 0$ . Then $H (X) \leq H (X^{2})$ fails, so the statement is not necessarily true.
(D) $Y = 2^{X}$ is strictly increasing, hence one-to-one, so $H (2^{X}) = H (X)$ and $H (X) \leq H (2^{X})$ holds. True.
Statements that are necessarily true: A, B and D.

KEY IDEA

Entropy depends only on the probability masses. A one-to-one function of $X$ leaves $H$ unchanged, a many-to-one function can only lower it, and $H (X) \leq lo g_{2} K$ for $K$ outcomes.

WATCH OUT FOR

Treating $X^{2}$ like $2 X$ or $2^{X}$ . Squaring merges the values $a$ and $- a$ , so $H (X^{2})$ can be smaller than $H (X)$ . The inequality $H (X) \leq H (X^{2})$ is therefore not guaranteed.

From the GATE 2022 EC paper. Every question of this paper · Download the full paper · All 9 Information theory questions, with notes

GATE 2022 EC Q.29: solution and answer

Answer and solution

More Information theory questions