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.

Problem statement:

The entropy of a probability vector $ p = (p_1, ... , p_n)^T $ is defined as $ H(p)= - \sum\limits_{i=1}^{n} p_i \log{p_i} $, subject to $ \sum\limits_{i=1}^{n} p_i = 1 \mbox{ and } p_i \geq 0$, where $ 0\log{0} = 0 $ by convention.

What is the largest and smallest entropy of any probability vector?

Discussion

I can maximise the expression using Lagrange multipliers without a problem. It's also equally easy to prove that the smallest entropy of any probability vector is 0, by noting that it must be non-negative, and providing an example with entropy 0.

However, I would very much like to prove that the minimum value is 0 using Lagrange multipliers (the fact that I can't seems to me to suggest that there is something that I haven't understood).

I set up the Lagrangian: $ L(p, \lambda) = - \sum p_i\log{p_i} + \lambda(\sum p_i - 1) $ and by differentiating to find stationary points obtain the system: $ {\frac{\partial{L}}{\partial{p_i}}}= -\log{p_i} - 1 + \lambda = 0 $. The obvious solution to this gives me my maximum point, but I am expecting another solution for the minimum.

  • Am I misusing Lagrange multipliers?
  • Is there another solution to my system that I am missing (maybe involving the "convention" about $ 0\log{0} = 0$)?
  • Do I need to worry about slackness and the condition $p_i \geq 0$ to find the minimum?
  • Is finding this minimum beyond the scope of this method for some reason, and my lecturers are in fact expecting me to resort to the "easy" method described above?

Any hints or answers are welcome, thank you in advance.

share|improve this question
    
The inequality constraints do not appear in the Lagrangian, so can have no 'effect'. A bigger issue is that the objective is not differentiable at the boundary. In this case, it would be more straightforward to note that $H(p) \geq 0$, and that $H(p) = 0$ is only attained when each $p_i$ is 0 or 1. –  copper.hat Oct 3 '12 at 18:34
    
Hi, thank you for your answer - I hadn't understood that the Lagrange method fails to provide extrema that lie on the boundary of the set of possible values for p. –  Joshua Pepper Oct 3 '12 at 19:00
    
There are two separate issues here. One is just the fact that the function is not differentiable on the whole domain. The second is that the inequality constraints $p_i \geq 0$ need to be incorporated. Handling the latter would involve a generalization using KKT conditions. Both are issues here. –  copper.hat Oct 3 '12 at 19:09

1 Answer 1

(the fact that I can't seems to me to suggest that there is something that I haven't understood).

Than something is more basic than Lagrange multipliers: is that extrema of functions not necesarily correspond to critical points (i.e. points where it's derivative is zero). You have to check also points where the function is not diferentiable, and/or the domain boundary.

For example, suppose you must have the extrema of the function $f(x)= (x-2)^3 - 3 x + 6$ in the domain $x \ge 0$ . Setting the derivative to zero, you get the critical points $x_1 = 1$ (maximum) and $x_2 = 3$ (minimum). But you forget the minimum that occurs at $x_0 = 0$, which you must check individually.

The same applies to Lagrange multipliers, which also find extrema that corresponds to critical points (along a restricted curve).

share|improve this answer
    
Hi, thank you for your valuable insight. It turns out this was precisely the point that I was struggling with. Would I be correct in stating that the boundary of this particular problem is the union of all positive axes in R^n? –  Joshua Pepper Oct 3 '12 at 18:53
    
No, you need to consider the plane $p_1+\cdots+p_n = 1$ as well. –  copper.hat Oct 3 '12 at 18:59
    
Yes, you have $0\le p_i \le 1$, so the boundary is given here by $p_i =0$ for some $i$ (which already includes the case $p_j=1$) –  leonbloy Oct 3 '12 at 19:15
    
Let me try again with more precision - if $X$ is the set on which the Lagrangian operates (excluding the $\lambda$-dimension), satisfying $p_i \geq 0$, and $X(p) \subset X$ is the feasible set where $\sum p_i = 1$ , then the boundary $B_1$ of $X$ is the union of positive axes, $X(p)$ corresponds to the edges of an n-dimensional pyramid (right-angled at the origin) that do not intersect with the axes, and the boundary $B_2$ of $X(p)$ is $B_1 \cap X(p)$, corresponding to the vertices of the pyramid, excluding the origin. @copper.hat –  Joshua Pepper Oct 3 '12 at 19:17
    
The boundary $B_1 = \{ (p_1, p_2 \cdots p_n) : p_1=0 \cup p_2=0 \cup \cdots \cup p_n=0\}$ is rather made of the union of the faces of that piramid, not the edges. You can also consider the union of the faces of the unitary hipercube. –  leonbloy Oct 3 '12 at 19:23

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.