MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to maximize the function $$f_s(k)=\frac{1}{2k+s}\sum_{i=0}^k {2k+s\choose i}2^{-(2k+s)}$$ for both $\{s,k\}\in\mathbf N$, that is, for fixed $s$ what is the value of $k$ that maximizes $f_s(k)$. I have seen previous discussions in Sum of 'the first k' binomial coefficients for fixed n and Lower bound for sum of binomial coefficients? but I'm not seeing much light. I'd be happy enough with a partial result, for instance a lower bound on the maximum value and the $k$ achieves it, or the range in which the maximum $k$ is to be found.

Anyone any idea?

share|cite|improve this question
up vote 3 down vote accepted

Using Stirling's formula one sees that $\binom{n}{n/2+\ell}$ is about $$ \sqrt{\frac{2}{\pi n}} 2^{n} e^{-2\ell^2/n}, $$ when $\ell$ is not too large. You can use this to evaluate your sum.

Let's look at the range when $k$ is of size about $s^2$ which is where the maximum will be attained. Writing $n=2k+s = s^2/t$ your sum is approximately $$ \frac{1}{\sqrt{2\pi} s^2} \left( t \int_{\sqrt{t}}^{\infty} e^{-x^2/2} dx\right). $$ Choose $t$ such that the term in brackets is maximum -- this is not any nice constant so far as I know, it is what it is. It then follows that your maximum sum is roughly $C/s^2$ for some constant $C$.

A calculation shows that $t$ above is roughly $1.42$, and that $C$ is about $0.165$. Note that then $k$ is about $s^2/2.84$. This is in rough agreement with the $s^2/3$ seen in Meyerowitz's answer; also when $s=100$ the asymptotic $0.165/s^2$ is very close to the $s^{-2.38}$ seen there.

share|cite|improve this answer

It would appear based on small computations that for fixed $s$ the maximum occurs for $k$ roughly $\frac{s^2}{3}.$ Perhaps that maximum is very roughly $\frac{1}{s^2\sqrt{s}}.$

Here are the optimal $k$ values up to $s=20$: $$[1, 1], [2, 1], [3, 1], [4, 1], [5, 3], [6, 6], [7, 9], [8, 14], [9, 18], [10, 24], [11, 30]$$$$ [12, 37], [13, 45], [14, 53], [15, 62], [16, 72], [17, 82], [18, 93], [19, 105], [20, 118]$$ For $12 \le s \le 60$ the optimal $k$ is the integer closest to $0.3531s^2-1.236s+1.13.$ The latter value is sometimes above and sometimes below the rounded value. I started at $s=12$ just because that is the first time that $\frac{s^2}{4}$ is not enough. The only reason I stop at $60$ is because that is as far as I looked. A slightly better fit can be achieved by using more decimal places and/or starting the range higher. This is just a poor computational result, but perhaps it tells one to try to prove that $0.4s^2$ is too much and $0.25s^2$ is not enough for $s \ge 12$.

With a slight adjustment, the rounded quadratic fit for the optimal $k$ holds at least as far as $s=100$ at which point $f_k(s) \approx s^{-2.386}.$ The appropriate exponents at $s=25,50$ and $75$ are $-2.533,-2.449$ and $-2.41$

share|cite|improve this answer

Well, if $k \gg s,$ if you remove the outer $1/(2k+s)$ factor you are just estimating the left tail of the normal distribution (you can multiply by the $1/(2k+s)$ later). If $k \ll s$ you are estimating the left tail of the Poisson distribution. Both are quite easy, and should give you reasonable estimates. For $k$ and $s$ of the same order, this is a standardish large-deviation estimate (again, easy to find in the literature). This will not give you precise values of $k,$ but will give you very good bounds.

share|cite|improve this answer

Your Answer


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.