0
$\begingroup$

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*}

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – grybouilli
    Commented Dec 7, 2021 at 10:03
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I'm not sure I understand how you go from the first to the second line of your equations, could you elaborate please? $\endgroup$
    – grybouilli
    Commented Dec 5, 2021 at 13:59
  • $\begingroup$ @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. $\endgroup$ Commented Dec 5, 2021 at 14:04
  • $\begingroup$ 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? $\endgroup$
    – grybouilli
    Commented Dec 5, 2021 at 14:11
  • $\begingroup$ @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). $$ $\endgroup$ Commented Dec 5, 2021 at 14:15
  • $\begingroup$ 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? $\endgroup$
    – grybouilli
    Commented Dec 5, 2021 at 14:20

You must log in to answer this question.

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