Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 –  Gerhard Paseman Nov 20 '11 at 5:59
    
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 –  Gerhard Paseman Nov 20 '11 at 18:21
    
Great! Let me know if you have some insight. –  Norouzi Nov 21 '11 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.

share|improve this answer
    
Thanks! How about if n or s doesn't go to infinity. Can we still say something? –  Norouzi Nov 21 '11 at 2:49
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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