# An optimization problem involving sum of binomial coefficients upto some value

I would like to minimize $f(s, n, \epsilon)$ with respect to $s$ where $$f(s,n,\epsilon) = \left( 1 + \frac{n}{2^s} \right)\frac{1}{s} \sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k}~.$$ Note that $0 < \epsilon < \frac{1}{2}$ and $n > 0$. Clearly optimal $s$ is going to be a function of $\epsilon$ and $n$, which might be ugly. However, I think $s^*$ should be close to $\log_2{n}$, based on the intuition from the problem giving rise to this, but I cannot find any rigorous argument for this choice of $s^*$. Any hint or idea is highly appreciated.

The following upper bound might be helpful: $$\sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k} \le 2 ^ {H(\epsilon)s }$$ where $H(\epsilon) \equiv -\epsilon \log \epsilon -(1-\epsilon) \log(1-\epsilon)$; the entropy of a Bernoulli dist. with probability $\epsilon$.

I don't know of any clean lower bound. Any idea?

I assume you have $n\to\infty$. If $\epsilon<\frac12$ and $s\to\infty$ then $$\sum_{k=0}^{\lfloor \epsilon s\rfloor} \binom{s}{k}$$ is very close to a geometric progression at the big end. Together with Stirling's approximation (ignoring the floor), this gives $$\sum_{k=0}^{\lfloor \epsilon s\rfloor} \binom{s}{k} \approx \frac{1-\epsilon}{1-2\epsilon}\binom{s}{\lfloor \epsilon s\rfloor} \approx \frac{1}{\sqrt{2\pi s}}\frac{1-\epsilon}{1-2\epsilon} (\epsilon(1-\epsilon))^{-s-1/2}.$$ Now you can look for the minimum wrt $s$ by differentiating. I don't get a closed form but it seems that the minimum is around $s=\log_2(n)+O(1)$.
ADDED: Note that the function is not continuous. Due to the floor function, it jumps up by a ratio close to $(1-\epsilon)/\epsilon$ as $\epsilon s$ passes an integer. So there are very many local minima. However, the global minimum ought to be close to the minimum of the function without the floor.
• It should be possible to develop precise error bounds on the approximations I gave, which will lead to some precise bounds on where the minimum is that all be valid if $n$ is large enough (going to $\infty$ won't be necessary). Extra terms in the approximations could be added. It would be a bit messy. – Brendan McKay Nov 21 '11 at 10:05