Tight upper bound for $\sum_{i=1}^{d} \log_{2} (c_{i})$ where $d>0, c_{i}>0$ and $\sum_{i=1}^{d}c_{i} \leq n$

Question

I would like to bound the above summation by something that is not dependent on $d$. One trivial upper bound would be to say that it is $O(d\log_{2} (n))$. If we change the summation so that it is $\sum_{i=1}^{d} c_{i}$ then the bound becomes $O(n)$ no matter how big $d$ is. Since $\log_{2}(x) < x$ for all $x>0$ we can also bound the original summation by $O(n)$. Can we do better than $O(n)$? Can we actually bound it by $O(\log n)$?

Answer 1

I am going to use natural logarithms instead. You can divide by $\ln 2$ at the end of the calculation.

First, by Jensen's inequality, $$ \frac1d\sum_{i=1}^d\ln c_i\le\ln\Bigl(\frac1d\sum_{i=1}^d c_i\Bigr) . $$ Multiplying by $d$ and using the assumption, we get $$ \sum_{i=1}^d\ln c_i\le d\ln\frac nd . $$ For any given $n$, this is sharp, since putting $c_i=n/d$ turns the inequality into an equality.

You want an estimate independent of $d$, so take the maximum value of the RHS when $d$ varies. Using standard calculus methods, you find that this happens when $d=n/e$. This might not be an integer, but never mind – when $n$ is large, rounding off to the nearest integer will not change the answer much. The resulting estimate is going to be $$ \sum_{i=1}^d\ln c_i\le \frac ne. $$ This is not sharp for any fixed $n$, due to the stated rounding issues – but asymptotically, as $n\to\infty$, it should be quite sharp.