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$ – Mateusz Kwaśnicki Oct 18 '19 at 12:48
  • 1
    $\begingroup$ @user64494 Yes, I definitely want an analytical solution as written in the post $\endgroup$ – user297646 Oct 18 '19 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$ – Dima Pasechnik Oct 19 '19 at 23:29
  • 1
    $\begingroup$ Is $H(Y)$ concave? $\endgroup$ – Dima Pasechnik Oct 19 '19 at 23:30
  • 1
    $\begingroup$ @Dima Pasechnik Yes, H is concave, I have also added the definition $\endgroup$ – user297646 Oct 20 '19 at 0:05
3
$\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$
2
$\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 '19 at 11:12
  • $\begingroup$ Can Maple write down the Hessian of f? $\endgroup$ – Dima Pasechnik Oct 20 '19 at 14:54
  • $\begingroup$ (I was not the downvoter, to the contrary...) $\endgroup$ – Dima Pasechnik Oct 20 '19 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$ – user297646 Oct 20 '19 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$ – Dima Pasechnik Oct 20 '19 at 19:22

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.