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.

  • $\begingroup$ Pretend the sum is bounded by l*2^s and u*2^s. I get that the 1/s term dominates and that no minimum is achieved as s goes to infinity. In particular, passing from s to s+1, you will often get a decrease. If epsilon is small, a good lower bound is (s+1) choose epsilon*s. Gerhard "Ask Me About System Design" Paseman, 2011.11.19 $\endgroup$ Nov 20, 2011 at 5:59
  • $\begingroup$ I see my silly mistake now. Indeed the minimum will occur for s > 2/epsilon and less than Clog n. I hope to give details on C soon. Gerhard "Ask Me About System Design" Paseman, 2011.11.20 $\endgroup$ Nov 20, 2011 at 18:21
  • $\begingroup$ Great! Let me know if you have some insight. $\endgroup$
    – Norouzi
    Nov 21, 2011 at 1:03

1 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.

  • $\begingroup$ Thanks! How about if n or s doesn't go to infinity. Can we still say something? $\endgroup$
    – Norouzi
    Nov 21, 2011 at 2:49
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 21, 2011 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.