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}~.$$ 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{n}$, based on the intuition from the problem giving rise to this, and the first term in $f(s, n, \epsilon)$. 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.