Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have recently encountered variants of the following expression: \begin{equation} S = H(a,b,c,d)-H(a+b,c+d) \end{equation} where $H$ is the Shannon entropy function, that is $H(X)=\sum_{x\in X}-x\log x$. And restrictions: \begin{eqnarray} a + b &=& t\\ a + c &=& t\\ a + b +c + d &=& 1 \end{eqnarray} for some given $t$. It is supposed to be easy to maximize this expression with Lagrange multipliers but I am unfamiliar with them so any hint in how $S$ can be optimized would be welcome.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Presumably $a,b,c,d > 0$ are required. In order for this to be possible, $0 < t < 1$. You should actually check the limits as one or more of $a,b,c,d$ go to $0$, but I will not do so. Putting in a Lagrange multiplier $\lambda_i$ for each constraint, the Lagrangian is $$L = -a\ln \left( a \right) -b\ln \left( b \right) -c\ln \left( c \right) -d\ln \left( d \right) + \left( a+b \right) \ln \left( a+b \right) + \left( c+d \right) \ln \left( c+d \right) +\lambda_{{1}} \left( a+b-t \right) +\lambda_{{2}} \left( a+c-t \right) +\lambda_{{3 }} \left( a+b+c+d-1 \right)$$ Now solve the system of equations obtained by setting to $0$ the derivative of $L$ with respect to each of the variables $a,b,c,d,\lambda_1, \lambda_2,\lambda_3$: $$ \eqalign{ a+b-t &= 0\cr a+c-t &= 0\cr a+b+c+d-1 &= 0\cr -\ln(d)+\ln(c+d)+\lambda_3 &=0\cr -\ln(b)+\ln(a+b)+\lambda_1+\lambda_3 &= 0\cr -\ln(c)+\ln(c+d)+\lambda_2+\lambda_3 &=0\cr -\ln(a)+\ln(a+b)+\lambda_1+\lambda_2+\lambda_3 &= 0\cr}$$ obtaining $$ a={t}^{2},b=c=t-{t}^{2}, d=(t-1)^2,\lambda_1 = 0,\lambda_{{2 }}=\ln(t/(1-t)) , \lambda_{{3}}=\ln (1-t) $$

share|improve this answer

Another approach is to avoid Lagrange multipliers. Solve the system of constraints for $b$, $c$, and $d$ to find $$\begin{eqnarray*} b &=& t-a \\ c &=& t-a \\ d &=& a-2t+1. \end{eqnarray*}$$ We have the restrictions $0\le a,b,c,d \le 1$, so $\textrm{max}(0,2t-1)\le a\le t$, where $0\le t\le 1$.

Thus, $$\begin{equation*} S(a) = H(a,t-a,t-a,a-2t+1)-H(t,1-t), \end{equation*}$$ so the extremum is the solution to $$\frac{\partial}{\partial a} H(a,t-a,t-a,a-2t+1) = 0,$$ or $a = t^2$, reproducing the solution found by @RobertIsrael. The maximum is $S_{\mathrm{max}} = S(t^2) = (t-1)\log(1-t) - t\log t$.

Note that $b=0 \iff c=0 \iff a=t$, but $S(t) = H(t,0,0,1-t)-H(t,1-t) = 0$. Also $d=0 \iff a=2t-1.$

entropy plot for a=0 and d=0

Figure 1. Plot of $S_{\mathrm{max}}$ (black), and $S$ for $a=0$ (red) and $d=0$ (blue).

share|improve this answer
    
Ok, so a purely analytic approach works as well. I will sure find use of this alternative, much lighter, approach. Thanks! –  Euclean Jun 26 '12 at 12:56
1  
@Euclean: Glad to help. Lagrange multipliers start to show their power when the constraints are more complicated than a linear system. –  user26872 Jun 26 '12 at 16:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.