# Optimisation: $H(X_1) + H(X_2) +H(X_3) - H(X_1+X_2+X_3)$

Consider the following optimisation. $$\max [H(X_1) + H(X_2) +H(X_3) - H(X_1+X_2+X_3)],$$ where H denotes the Shannon entropy, + denotes addition over real numbers, and the maximum is taken over all the random variables $$X_1$$, $$X_2$$, $$X_3$$ that are independent Bernoulli.

Question: How to prove that the maximum is achieved when $$X_1$$, $$X_2$$, and $$X_3$$ follow a uniform distribution?

Edit (as requested): For a discrete random variable $$X$$ with probability mass function $$p$$ with support $$\mathcal{X}$$, $$H(X) = - \sum_{x \in \mathcal{X}} p(x) \log p(x)$$.

• Equivalent formulation: maximize the conditional entropy of $(X_1,X_2,X_3)$ given $X_1+X_2+X_3$, where $X_1$, $X_2$, $X_3$ are independent Bernoulli random variables (with possibly different parameters). – Mateusz Kwaśnicki Oct 18 '19 at 12:48
• @user64494 Yes, I definitely want an analytical solution as written in the post – user297646 Oct 18 '19 at 16:34
• Would you care to provide a (link to) an explict formula for $H(Y)$, for $H$ as in the latest displayed formula in the question? – Dima Pasechnik Oct 19 '19 at 23:29
• Is $H(Y)$ concave? – Dima Pasechnik Oct 19 '19 at 23:30
• @Dima Pasechnik Yes, H is concave, I have also added the definition – user297646 Oct 20 '19 at 0:05

Too long for a comment. Note that $$\bar{\bar{x}}=1-\bar{x}=1-(1-x)=x$$. Similar for $$y$$ and $$z$$. Denote $$u:=(x,y,z)$$ then $$\bar{u}=(\bar{x},\bar{y},\bar{z})$$. So your problem can be rewritten as $$\max_{u\in(0,1)^3}f(u)+f(\bar{u})$$ Note that if $$u^*\in\arg\max_{u\in(0,1)^3}f(u)+f(\bar{u})$$ then so is $$\bar{u}^*$$ because $$f(\bar{u}^*)+f(\bar{\bar{u}}^*)=f(\bar{u}^*)+f(u^*)=f_{\max}$$ It suffices therefore to prove that $$f(u)+f(\bar{u})$$ is a strictly concave function of $$u\in(0,1)^3$$ since in this case if a maximum exists it would be unique. This would force $$u^*=\bar{u}^*$$ or equivalently $$x^*=1-x^*,y^*=1-y^*,z^*=1-z^*$$ implying $$x^*=y^*=z^*=1/2$$.

Here is a partly analytic solution done in Maple 2017.3. First, the result of

f := -(1-x)*(1-y)*z*ln((1-x)*(1-y)*z/((1-x)*(1-y)*z+(1-x)*y*(1-z)+x*(1-y)*(1-z)))-
(1-x)*y*(1-z)*ln((1-x)*y*(1-z)/((1-x)*(1-y)*z+(1-x)*y*(1-z)+x*(1-y)*(1-z)))-
x*(1-y)*(1-z)*ln(x*(1-y)*(1-z)/((1-x)*(1-y)*z+(1-x)*y*(1-z)+x*(1-y)*(1-z)))-
(1-x)*y*z*ln((1-x)*y*z/((1-x)*y*z+x*(1-y)*z+x*y*(1-z)))-
x*(1-y)*z*ln(x*(1-y)*z/((1-x)*y*z+x*(1-y)*z+x*y*(1-z)))-
x*y*(1-z)*ln(x*y*(1-z)/((1-x)*y*z+x*(1-y)*z+x*y*(1-z))):
DirectSearch:-GlobalOptima(f, {x >= 0, y >= 0, z >= 0, x <= 1, y <= 1, z <= 1}, maximize);


$$[.823959216501083, [x = .500000007051357, y = .500000002907430, z = .499999998207894], 448]$$ means the global maximum of $$f$$ on the cube $$[0,1]^3$$ is reached at the point $$x = .500000007051357, y = .500000002907430, z = .499999998207894$$ with the absolute error $$10^{-6}$$ (see the help to DirectSearch). Second, the result of

DirectSearch:-SolveEquations([diff(f, x) = 0, diff(f, y) = 0, diff(f, z) = 0],
{x >= 0, y >= 0, z >= 0, x <= 1, y <= 1, z <= 1}, AllSolutions, solutions = 5);


$$\left[ \begin {array}{cccc} { 1.23259516440783095\times 10^{-32}}& \left[ \begin {array}{c} -{ 1.11022302462515654\times 10^{-16}} \\ 0.0\\ 0.0\end {array} \right] &[x= 0.500000000000000000,y= 0.499999999999999944,z= 0.499999999999999944]&154\end {array} \right]$$ means there is only one critical point of $$f$$ inside the cube $$[0,1]^3$$ and this point is close to $$x=\frac 1 2,y= \frac 1 2,z=\frac 1 2$$. It is easy to verify that the point $$x=\frac 1 2,y= \frac 1 2,z=\frac 1 2$$ is a critical point of $$f$$. Third, the results of

Student[MultivariateCalculus]:- SecondDerivativeTest(f, [x,y,z] = [1/2, 1/2, 1/2],output='hessian');


$$\left[ \begin {array}{ccc} -8/3&-\ln \left( 3 \right) +4/3&-\ln \left( 3 \right) +4/3\\ -\ln \left( 3 \right) +4/3 &-8/3&-\ln \left( 3 \right) +4/3\\-\ln \left( 3 \right) +4/3&-\ln \left( 3 \right) +4/3&-8/3\end {array} \right]$$ and

Student[MultivariateCalculus]:- SecondDerivativeTest(f, [x, y, z] = [1/2, 1/2, 1/2]);


$${\it LocalMin}=[],{\it LocalMax}=[[1/2,1/2,1/2]],{\it Saddle}=[]$$

mean that the critical point $$x=\frac 1 2,y= \frac 1 2,z=\frac 1 2$$ is the maximum point. Summing up the above, we conclude, that the global maximum is reached at.

• @the downvoter: What is bad in my answer? TIA. – user64494 Oct 20 '19 at 11:12
• Can Maple write down the Hessian of f? – Dima Pasechnik Oct 20 '19 at 14:54
• (I was not the downvoter, to the contrary...) – Dima Pasechnik Oct 20 '19 at 15:06
• @user64494 Thanks! Unfortunately, it does not provide an analytic proof, that's why I do not validate it as an answer to the post – user297646 Oct 20 '19 at 16:50
• the question about the Hessian would be to see whether it is negative definite on the domain we maximize. – Dima Pasechnik Oct 20 '19 at 19:22