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!
$\begingroup$
$\endgroup$
6
-
$\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$– assumednormalNov 28, 2015 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$– VimalNov 28, 2015 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$– assumednormalNov 28, 2015 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$– VimalNov 28, 2015 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_106Nov 30, 2015 at 2:10
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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.