= Solution
\b[The inequality is true] for ordinary addition, and also for addition in a <group>. For any fixed $y$, the translation $x\mapsto x+y$ is <injective>, so it merely relabels the <probability masses> in the <conditional distribution>. Since $X,Y$ are <independent random variables>,
$$
H(X+Y\mid Y=y)=H(X\mid Y=y)=H(X).
$$
Averaging over $y$ and using <conditioning reduces entropy> proves <entropy monotonicity under independent addition>:
$$
\boxed{H(X+Y)\geq H(X+Y\mid Y)=H(X).}
$$
There is no requirement that $X+Y$ remain in the original <finite alphabet>. The proof also gives $H(X+Y)\geq H(Y)$ by symmetry. Independence matters: for a nonconstant $X$ and $Y=-X$, the sum is constant while $H(X)>0$.
Back to article page
