An optimization problem involving sum of binomial coefficients upto some value

Question

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?

Thanks for your time in advance.

Answer 1

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.