Is $H(f(X))$ a concave function in $p(x)$?

Question

$H(X)=-\sum_{x}p(x)\log {p(x)}$ is the entropy of a random variable $X$. I know that it is a concave function of $p(x)$. But is it still true that $H(f(X))$ is a concave function forall function $f(\cdot)$ w.r.t. $p(x)$?

Answer 1

Let $q$ be the distribution of $Y = f(X)$. Then notice that $q$ is a linear function of $p$. Indeed, we have that $q(y) = \sum_{x : f(x) = y} p(x)$. Let $M$ be the $|\mathcal{Y}| \times |\mathcal{X}|$ matrix for which the entry $M_{y,x}$ is $1$ if $y = f(x)$, and $0$ otherwise. Then observe that $q = Mp$.

Therefore, the entropy of $f(X)$ is $H(Mp),$ where we know that $H(\cdot)$ is a concave function. But the composition of a concave and a linear function is concave. Indeed, for $t \in [0,1],$ and distributions $p, p',$ the output distribution under the mixture input $tp + (1-t) p'$ is $M(tp + (1-t)p'),$ and we have \begin{align} H(M (tp + (1-t)p')) &= H(t Mp + (1-t)Mp')\\ &\ge t H(Mp) + (1-t) H(Mp'),\end{align} and we're done.