Maximize a weighed combinatorial sum

Question

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?

Answer 1

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.

Answer 2

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$

Answer 3

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.