0
$\begingroup$

Let $v_1<\cdots<v_n$ and $\mu\in(v_1,v_n)$ be real numbers. Consider set $$X=\left\{(p_1,\ldots,p_n)\in[0,1]^n\ |\ \sum_{i=1}^np_i=1,\ \sum_{i=1}^np_iv_i=\mu\right\},$$ which is convex (easy) and compact. Consider entropy $$H:X\to\mathbb R,\ H(p_1,\ldots,p_n)=-\sum_{j=1}^np_j\log_2p_j,$$ and let us look for maximum. $H$ is strictly concave continuous function on compact convex set, therefore there is unique $x^*\in X$ such that $H(x^*)=\max\{H(x)\,|\,x\in X\}.$ Construct Langrangian as \begin{align*} \mathcal{L}(p_1,\ldots,p_n;\lambda_1,\lambda_2)&=-\sum_{j=1}^np_j\log_2p_j+\lambda_1\left(1-\sum_{j=1}^np_j\right)+\lambda_2\left(\mu-\sum_{j=1}^np_jv_j\right)= \\ &=\lambda_1+\lambda_2\mu-\sum_{j=1}^np_j\left(\lambda_1+\lambda_2v_j+\log_2p_j\right), \end{align*} from which I received system of $n+2$ equations $$p_j=2^{-\lambda_1-\lambda_2v_j}/e,\quad\sum_{k=1}^np_k=1,\quad\sum_{k=1}^np_kv_k=\mu.$$

Now, I would like to provide a reason that the previous system has a solution. Moreover, if the solution were unique, I would not need to bother with the boundary points. But is there any feasible way how to show that? (I want to avoid second partial derivative test.)

At first, I thought the maximum cannot be achieved on a boundary, but $[-1,0]\to\mathbb R,x\mapsto -x^2$ provides a counterexample.

$\endgroup$
  • $\begingroup$ Look at Weierstrass' Theorem and at strict convexity. Uniqueness does not mean that the solution cannot be on the boundary. $\endgroup$ – LinAlg Mar 8 at 0:24
  • $\begingroup$ @LinAlg Is that just a general comment? Because, I'm sorry, but is it useful? $\endgroup$ – byk7 Mar 11 at 13:56
  • $\begingroup$ It answers some of your question. "I would like to provide a reason that the previous system has a solution" is answered by Weierstrass' theorem, and "if the solution were unique" is answered by strict convexity. Overall, the KKT conditions should help you find the solution. $\endgroup$ – LinAlg Mar 11 at 14:09
  • $\begingroup$ @LinAlg Still I feel like I miss something. If the maximum is attained on the boundary, then the system does not have a solution, so how does Weierstrass' theorem work here? $\endgroup$ – byk7 Mar 11 at 17:02
0
$\begingroup$

Plug $p_j=2^{-\lambda_1-\lambda_2v_j}/e$ into the last two equations \begin{align*} &\sum_{k=1}^np_k=1\ \ \Rightarrow\ \ \sum_{k=1}^n2^{-\lambda_1-\lambda_2v_k}/e=1\ \ \Rightarrow\ \ \sum_{k=1}^n2^{-\lambda_2v_k}=e2^{\lambda_1} \\ &\sum_{k=1}^np_kv_k=\mu\ \ \Rightarrow\ \ \sum_{k=1}^nv_k2^{-\lambda_1-\lambda_2v_k}/e=\mu\ \ \Rightarrow\ \ \sum_{k=1}^nv_k2^{-\lambda_2v_k}=e\mu2^{\lambda_1} \\ &\Longrightarrow\ \ \sum_{k=1}^nv_k2^{-\lambda_2v_k}=\mu\sum_{k=1}^n2^{-\lambda_2v_k}\ \ \Rightarrow\ \ \sum_{k=1}^n(v_k-\mu)2^{-\lambda_2v_k}=0 \end{align*} and the last equation has a solution.

Second partial derivative test says it would be a maximum as $p_j>0.$ (In fact, the test is quite pleasant since the Hessian is a diagonal matrix.) The obtained solution is unique from strict concavity. (Hence, there is no maximum on the boundary.)

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