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.