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

Question

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

Answer 1

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.

Answer 2

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.