1
$\begingroup$

What is the tightest upper bound one can obtain for the following expression

$$\sum_{i=1}^kA_i\log(\frac{A_i}{e})$$ subject to $\sum_{i = 1}^k A_i = C$ in terms of $C$ and $k$?

A very loose upper bound for this expression is $C\log(\frac{C}{e})$. Can we do better than this?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Something's wrong here: when all $A_i$ approach $0$ except for $A_1$, then the sum converges to $C \log(C/e)$, which is greater than your upper bound. $\endgroup$
    – Mateusz Kwaśnicki
    May 6, 2017 at 23:10
  • $\begingroup$ Lagrange multipliers tell you that this is maximized when $A_i = C/k.$ $\endgroup$
    – Igor Rivin
    May 6, 2017 at 23:10
  • 1
    $\begingroup$ @IgorRivin does not that minimize the function? I mean, $x\log(x/e)$ is convex, not concave. $\endgroup$
    – Vladimir Dotsenko
    May 6, 2017 at 23:34
  • $\begingroup$ @VladimirDotsenko very true. I guess I will have to answer the question then :( $\endgroup$
    – Igor Rivin
    May 7, 2017 at 0:27
  • $\begingroup$ @MateuszKwaśnicki you are correct. My given upper bound was assuming $A_i \geq 1$ which is not in general true. $\endgroup$
    – user109523
    May 7, 2017 at 3:15

1 Answer 1

Reset to default
5
$\begingroup$

The gradient of your function is $(\log A_1, \dotsc, \log A_n).$ The function is convex, and so the minimum can be seen, by Lagrange multipliers to occur when all of the $A_i$ are equal (to $C/k$). So, the minimum value of the function is $$C \log\left(\frac{C}{ke}\right).$$

On the other hand, the maximum must occur on the boundary, which is to say, when some of the $A_i$ are $0.$ It is clear that in fact for a maximum, all but one $A_i$ are $0,$ on which case (since $\lim_{x\to 0} x \log x = 0$), the value is $C \log\frac{C}{e}.$.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Just a comment: This is a typical problem that chooses a discrete distribution supported on simplex which maximizes the entropy w.r.t. the discrete uniform. $\endgroup$
    – Henry.L
    May 7, 2017 at 1:30

Your Answer

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

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