3
$\begingroup$

Let $X_1$ & $X_2$ be two independent binary r.v.s, taking values in {0,1}; let $Y \triangleq X_1+X_2$ be their sum, i.e. a ternary r.v. taking values in {0,1,2}. How do we prove that the maximum value of $H(Y)$ is 1.5 (bits)? Note that with $X_1$ & $X_2$ being i.i.d. Bern($\frac{1}{2}$), a simple caculation shows that the entropy of the sum is 1.5 bits. However, I'm having difficulty proving that this is indeed its maximum value, and would appreciate some help. Thanks a lot!

$\endgroup$
  • $\begingroup$ Think of $X_1$ and $X_2$ as general Bernoulli random variables with $P\left(X_1=0\right)=P\left(X_2=0\right)=p$. Write $H\left(Y\right)=H\left(X_1+X_2\right)$ as a function of $p$, differentiate, set equal to 0, and solve for $p$. To ensure that you've found a $p$ that maximizes $H$, check that the second derivative of $H$ at $p$ is less than $0$. $\endgroup$ – Max Nov 28 '15 at 11:20
  • $\begingroup$ @Max this assumes that $X_1$ and $X_2$ are identically distributed, something which isn't stated in the question. $\endgroup$ – Vimal Nov 28 '15 at 15:06
  • 1
    $\begingroup$ @Vimal You're right, though It's not a giant leap to go from the case where $X_1$ and $X_2$ are identically distributed to the case where they're not. If $P\left(X_1=0\right)=p_1$ and $P\left(X_2=0\right)=p_2$: write $H\left(Y\right)=H\left(X_1+X_2\right)$ as a function of $p_1$ and $p_2$, differentiate, set equal to $0$, and solve for the values of $p_1$ and $p_2$ that jointly maximize the value of $H$. Again, check the second derivative to ensure you've found a maximum of $H$ rather than a minimum or saddle point. $\endgroup$ – Max Nov 28 '15 at 15:48
  • 2
    $\begingroup$ @Max yes, that's right, it shouldn't be hard. I was just curious to see if there's a nicer argument than brute force. It isn't quite obvious that the entropy of $X_1 + X_2$ for arbitrary distributed $X_1$ and $X_2$ will be 1.5 bits and not $\log_2(3)$ bits. $\endgroup$ – Vimal Nov 28 '15 at 17:07
  • $\begingroup$ @Max Thanks, Max & Vimal, for the comments! (Sorry I was away yesterday.) Yeah, I had tried the analysis approach. However, the solution wasn't evident. Specifically, if we let $X_1 ∼Bern(a),X_2 ∼Bern(b)$, and define $f(a,b)=H(Y)$, then the components of the gradient vector of $f$ are $$f_a(a,b)=(1−b)log(1−a)(1−b)−(1−2b)log(a+b−2ab)−blog(ab)$$ $$f_b(a,b)=(1−a)log(1−a)(1−b)−(1−2a)log(a+b−2ab)−alog(ab)$$ . It's simple to check that $\triangledown f(0.5,0.5)=[0,0]$, but it's not evident to me if this is the only solution. So, as Vimal commented, I was wondering if there's a simpler approach. $\endgroup$ – syeh_106 Nov 30 '15 at 2:10
3
$\begingroup$

One approach is to formulate it as an analysis problem, as Max also suggested above. A few tricks & observations will simplify the solution.

Let $X_1 \sim Bern(a), X_2 \sim Bern(b),$ and $Y \triangleq X_1+X_2,$ where $a,b \in [0,1].$ Defining $f(a,b) \triangleq H(Y),$ it follows that $$f(a,b) = -(1-a)(1-b)log(1-a)(1-b) - ab\ log(ab) -(a+b-2ab)log(a+b-2ab)$$

First of all, $f$ is a continuous function on $S \triangleq [0,1]\times[0,1]$, which is a compact set. So a maximum of $f$ must exist on $S.$

Secondly note that if $a = 0$ or $1$, then $f(a,b)=H(Y)=H(X_2)\leq 1$ bit. Similarly, if $b=0$ or $1$, then $f(a,b)\leq 1$ bit. So a maximum of $f$ does not occur on the boundary of $S$, because $f(0.5,0.5)=1.5$ bits$>1$ bit. It must occur in $int\ S,$ i.e.$(0,1)\times(0,1)$.

To simplify the analysis,let's use natural log from this point on. Since $f \in C'$ on $int\ S$, with $$f_a(a,b)=(1−b)log(1−a)(1−b)−(1−2b)log(a+b−2ab)−b\ log(ab),$$ $$f_b(a,b)=(1−a)log(1−a)(1−b)−(1−2a)log(a+b−2ab)−a\ log(ab).$$ It follows that a maximum must satisfy $\triangledown f = [0,0].$ Now note that $$f_a(a,b)=0 \Leftrightarrow (1-b)log\frac{(1-a)(1-b)}{a+b-2ab}=b\ log\frac{ab}{a+b-2ab}$$ $$f_b(a,b)=0 \Leftrightarrow (1-a)log\frac{(1-a)(1-b)}{a+b-2ab}=a\ log\frac{ab}{a+b-2ab}$$ To solve this set of equations, it helps to note that the log's above are well-defined on $int\ S$. Moreover, they cannot both be zero, because $X_1$ & $X_2$ are independent. As a result, neither of them can be zero; otherwise the equalities above cannot hold. This observation greatly simplifies the solution, because it implies that $$\frac{a}{1-a}=\frac{b}{1-b},$$ which in turn implies $a=b.$

Substituting $a=b$ into $f_a(a,b)=0$, with some simplification, we have $$g(a)\triangleq log\frac{1-a}{2a}+2a\ log2=0.$$ Note that $a=0.5$ is clearly a solution. To prove that this is the only solution, it suffices to show that $g(a)$ is strictly decreasing on $(0,1).$ This can be easily seen by differentiating $g(a)$, and noting $$g'(a)=2\ log2-\frac{1}{a(1-a)}< 0,$$ for all $a \in (0,1).$ We therefore conclude $a=b=0.5$ is the only solution of $\triangledown f=[0,0]$ on $int\ S$. So $f(0.5,0.5) = 1.5$ (bits) is indeed the maximum. This completes the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.