Let $X\in\{x_1,x_2\}$ be a real binary random variable with probability mass function $\{p_1,p_2=1-p_1\}$. Let $N$ be a real random variable with standard normal distribution (mean = $0$, std = $1$). Let $Y=X+N$. Let $H(Y)$ denote the differential entropy of $Y$.

It seems like it should be easy to prove that $H(Y)$ increases as $|x_1-x_2|$ increases, that is, as the distance between the two sample points of the binary random variable increases. This is motivated by the mutual information of the output of an additive Gaussian noise channel with binary input; for a given noise power, the mutual information is maximized by spreading the two points as far as possible (subject to whatever constraints one has). The mutual information is

$$I(X;Y) = H(Y) - H(Y|X) = H(Y)-H(N)$$

Since the mutual information is increased by increasing the distance between $x_1$ and $x_2$, and since $H(N)$ is independent of $X$, $H(Y)$ must increase as $|x_1-x_2|$ increases.

I have tried to prove this from the definition of entropy and so far have been unsuccessful. We have

$$H(y) = -\int{p(y)\log\left(p(y)\right)dy} = -\int{\sum_{i=1}^2{p_i p_N(y-x_i)\log{\left(\sum_{i=1}^2{p_i p_N(y-x_i)}\right )}}dy}$$

I have tried using the fact that relative entropy is nonnegative and also the log sum inequality (Theorems 2.7.1 and 8.6.1 in Elements of Information Theory, Cover and Thomas, 2nd Edition). This seems like it should be simple, but I have had no luck. Do I need to use calculus of variations? Thank you in advance.


2 Answers 2


I worked out the proof of this, which was straightforward when I took a more direct approach.

Let $x_2=x_1+\Delta$. Let $g(n)$ be the pdf of a standard normal random variable. $$g(n)=\frac{1}{\sqrt{2\pi}}e^{-n^2/2}$$ The pdf of $Y=X+N$ is given by $$\begin{aligned} p(y) & = p_1 g(y-x1)+(1-p_1)g(y-x_2) \\ & = p_1 g(y-x1)+(1-p_1)g(y-(x_1+\Delta)) \end{aligned}$$ The entropy of $Y$ is given by $$H(Y)=-\int_{-\infty}^\infty{p(y)\log(p(y))dy}$$ So $$ \begin{aligned} \frac{d H(Y)}{d \Delta}& = -\int_{-\infty}^\infty{ \frac{d p(y)}{d \Delta}(\log(p(y))+1)dy } \\&=-(1-p_1)\int_{-\infty}^\infty{\bigl(y-(x_1+\Delta)\bigr)g\bigl(y-(x_1+\Delta)\bigr)\bigl(1+\log(p(y))\bigr)dy} & (1) \\&=-(1-p_1)\int_{-\infty}^\infty{yg(y)\bigl(1+\log(p(y+x_1+\Delta)\bigr)dy} & (2) \\&=-(1-p_1)\int_{-\infty}^\infty{yg(y)\log\bigl(p(y+x_1+\Delta)\bigr)dy} & (3) \\&=-(1-p_1)\int_{0}^\infty{yg(y)\log\bigl(p(y+x_1+\Delta)\bigr)-yg(-y)\log\bigl(p(-y+x_1+\Delta)\bigr)dy} & (4) \\&=(1-p_1)\int_{0}^\infty{yg(y)\log\left(\frac{p(-y+x_1+\Delta)}{p(y+x_1+\Delta)}\right)dy} & (5) \end{aligned} $$ (2) is a change of variables, (3) follows because $yg(y)$ is odd, (4) follows by changing the limits of integration, and (5) utilizes the fact that $g(y)$ is even.

Now $$\frac{p(-y+x_1+\Delta)}{p(y+x_1+\Delta)}= \frac{(1-p_1)g(y)+p_1 g(y-\Delta)}{(1-p_1)g(y)+p_1 g(y+\Delta)}$$

Further $$g(y+\Delta)=g(y-\Delta)e^{-2y\Delta}$$ Hence $$ \frac{d H(Y)}{d \Delta} = (1-p_1)\int_{0}^\infty{yg(y)\log\left(\frac{(1-p_1)g(y)+p_1 g(y-\Delta)}{(1-p_1)g(y)+p_1 g(y-\Delta)e^{-2y\Delta}}\right)dy} $$

For $\Delta=0$ (i.e., $x_1=x_2$), the argument of the $\log$ function is $1$ and the derivative is $0$. This is expected, since $H(y)=0$ (and therefore minimized) when $x_1=x_2$. Noting that the integral is only over nonnegative $y$, the argument of the log function is greater than $1$ for all $\Delta>0$, and it is less than $1$ for all $\Delta<0$. The integrand is therefore strictly positive for $\Delta>0$ and strictly negative for $\Delta<0$ over the range of integration for positive $y$. So the derivative has the same sign as $\Delta$, and $H(Y)$ increases monotonically as $|\Delta|$ increases.


I would argue that it is not the case actually. Indeed whether $X$ turns out to be $x_1$ or $x_2$ matters little since once it is fixed, you have that the output of the additive channel is a Normal random variable centered at $x_1$ or $x_2$. Moreover, since the entropy of a Normal random variable does not depend on its mean, this implies $H(Y|X) = H(N) = \frac12 \log(2\pi e)$.

More formally you have:

$\begin{align} H(Y) &= \sum_{i=1,2} H(Y|X=x_i)P(X=x_i)\\&=p_1H(Y|X=x_1) + p_2H(Y|X=x_2)\\&=p_1H(N)+p_2H(N)\\&=H(N)\\&=\frac12 \log(2\pi e), \end{align}$

which does not depend on $x_1$ or $x_2$.

Hope this helps!

  • 1
    $\begingroup$ Thank you for your reply. I am sure that what I was trying to prove is in fact correct, and I have since completed the proof. I will post it shortly. $\endgroup$
    – nlmath
    Feb 17, 2022 at 3:03
  • $\begingroup$ What you have derived above is the conditional entropy $H(Y|X)$, which is defined in Cover and Thomas eq (2.10), matching the first line of your derivation exactly. In fact, the mutual information $I(Y;X) = H(Y)-H(Y|X) = H(Y)-H(N)$. As the separation between the points goes to infinity, $H(y)$ goes to $\log(2)+H(N)$, so $I(Y;X)$ goes to 1 bit using base 2. $\endgroup$
    – nlmath
    Feb 17, 2022 at 3:10
  • $\begingroup$ When I said that $H(Y)$ approaches $H(N)+\log(2)$ as the separation of the points goes to $\infty$, I had in mind $p_1=p_2=1/2$. I should have said that the entropy approaches $H(N)+H(X)$, which is of course $H(N)+\log(2)$ for the case I mentioned. $\endgroup$
    – nlmath
    Feb 17, 2022 at 7:00

You must log in to answer this question.

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