# Proving an inequality on Shannon entropy (non increasing under functions)

Suppose I have a discrete random variable $$X:\Omega\to\mathcal{X}$$ and a function $$g:\mathcal{X}\to\mathcal{Y}$$. With $$\mathbb{H}$$ being the Shannon entropy, how do I prove: $$\mathbb{H}(g(X)) \leq \mathbb{H}(X)$$

I tried studying the difference between both members of the inequality, but I can't find a way of proving it's positive (given I'm working on $$\mathbb{H}(X) - \mathbb{H}(g(X))$$).

Edit: I found a proof in this paper: http://www.ece.tufts.edu/ee/194NIT/lect01.pdf but I wish to know if there is a way of doing it without the use of chain rules for two variables, by just using the expression of the Shannon entropy itself.

Edit 2 : Here is a proof using Sangchul Lee's answer (https://math.stackexchange.com/q/4324552)

Let $$Y=g(X)$$. For any $$x,y$$, we have $$\displaystyle p_{X|Y=y}(x) = \begin{cases} &\frac{p_X(x)}{p_Y(y)} \text{ when } g(x) = y \\ &0 \text{ otherwise}\end{cases}$$

Hence, \begin{align*} H(X)-H(Y) &= \mathbb{E}\left(-\log\left(\frac{p_X(X)}{p_Y(Y)}\right)\right) \\ &= -\sum_{x,y} p_{X,Y}(x,y)\log\left(\frac{p_X(x)}{p_Y(y)}\right) \\ &= -\sum_{y}\sum_x p_{X,Y}(x,y)\log\left(\frac{p_X(x)}{p_Y(y)}\right) \\ &= -\sum_{y}\sum_{x:g(x)=y} p_{X,Y}(x,y)\log\left(p_{X|Y=y}(x)\right)\\ &= -\sum_{y}\sum_{x:g(x)=y} p_{X|Y=y}(x)p_Y(y)\log\left(p_{X|Y=y}(x)\right)\\ &= -\sum_{y} p_Y(y)\sum_{x:g(x)=y} p_{X|Y=y}(x)\log\left(p_{X|Y=y}(x)\right)\\ &= \sum_y p_Y(y)H(X|Y=y) > 0. \end{align*}

You can also write

$$H(X,Y) = H(X) +H(Y|X) = H(Y) +H(X|Y)$$

Now, $$H(Y|X) = \sum_x P(X=x) H(Y |X=x)$$ . But $$H(Y |X=x)=0$$ , because for any given $$X=x$$, $$Y$$ is deterministic, i.e. $$P(Y| X=x)$$ equals $$1$$ for some $$y$$, zero elswhere.

Hence $$H(Y|X)=0$$ , and $$H(Y) = H(X)-H(X|Y) \le H(X)$$

because $$H(X|Y)\ge 0$$.

Equality occurs if $$H(X|Y)=0$$, that is, if knowing $$g(X)$$ one knows $$X$$; that is, if $$g(X)$$ is one-to-one.

• Indeed, it is the proof iI found here: ece.tufts.edu/ee/194NIT/lect01.pdf . Works well, but I wanted to see if there was a way of using only the entropy of single variables. Commented Dec 7, 2021 at 10:03

You can adapt the proof of the chain rule. Write $$Y = g(X)$$ for notational simplicity. Then

\begin{align*} H(X) - H(g(X)) &= - \mathbf{E}\left[ \log \frac{p_X(X)}{p_Y(Y)} \right] \\ &= - \sum_y p_Y(y) \mathbf{E}\left[ \log \frac{p_X(X)}{p_Y(y)} \,\middle|\, Y = y\right] \\ &= - \sum_y p_Y(y) \sum_{x : g(x) = y} p_{X\mid Y} (x \mid y) \log p_{X\mid Y} (x \mid y) \end{align*}

However, since $$x \mapsto p_{X\mid Y}(x \mid y)$$ is a p.m.f. for each $$y$$, we find that

$$-\sum_{x : g(x) = y} p_{X\mid Y} (x \mid y) \log p_{X\mid Y} (x \mid y) = H(p_{X \mid Y}(\cdot \mid y)) \geq 0.$$

Therefore the desired inequality follows.

• I'm not sure I understand how you go from the first to the second line of your equations, could you elaborate please? Commented Dec 5, 2021 at 13:59
• @grybouilli, It is the consequence of the law of total expectation. The equality between the first and last line can be verified in a more direct manner, though. Indeed you can check that the sum in the last line reduces to $H(X) - H(g(X))$ by writing $p_{X\mid Y}(x \mid y) = p_X(x) - p_Y(y)$ and simplifying the resulting sum. Commented Dec 5, 2021 at 14:04
• how is $p_{X|Y}(x|y) = p_X(x)-p_Y(y)$? Do you use the definition of conditionnal probabilities to get this result? Commented Dec 5, 2021 at 14:11
• @grybouilli, Yes, and in fact, that is the crucial part of this answer. To prove that equality, note that for $x, y$ satisfying $p_Y(y) > 0$, we get $$p_{X\mid Y}(x\mid y) = \mathbf{P}(X = x \mid Y = y) = \frac{\mathbf{P}(X = x, Y = y)}{\mathbf{P}(Y = y)}.$$ However, we know that $X$ determines the value of $Y = g(X)$. In particular, if $x$ is such that $g(x) = y$, then $X =x$ implies $g(X) = y$, and so, $$\mathbf{P}(X = x, Y = y) = \mathbf{P}(X = x).$$ Commented Dec 5, 2021 at 14:15
• Then when $x$ and $y$ satisfy $g(x)=y$, we have $p_{X|Y}(x|y) = \frac{p_X(x)}{p_Y(y)}$ and not $p_{X|Y}(x|y) = p_X(x) - p_Y(y)$ right? Commented Dec 5, 2021 at 14:20