7
$\begingroup$

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)$.

$\endgroup$
12
  • 1
    $\begingroup$ 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). $\endgroup$ Oct 18, 2019 at 12:48
  • 1
    $\begingroup$ @user64494 Yes, I definitely want an analytical solution as written in the post $\endgroup$
    – user83947
    Oct 18, 2019 at 16:34
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 19, 2019 at 23:29
  • 1
    $\begingroup$ Is $H(Y)$ concave? $\endgroup$ Oct 19, 2019 at 23:30
  • 1
    $\begingroup$ @Dima Pasechnik Yes, H is concave, I have also added the definition $\endgroup$
    – user83947
    Oct 20, 2019 at 0:05

2 Answers 2

3
$\begingroup$

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.

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.