4
$\begingroup$

If we define

$ S = \sum_{k=1}^{\lceil n/2 \rceil} \binom n k \left(\frac{k}{n}\right)^{2k} \left(1 - \frac{k}{n}\right)^{2(n-k)} $

Then when $n\to \infty$, does $S \to 0$?

  • 0
    It seems like this result should have some combinatoric/probabilistic interpretation, perhaps in terms of the central limit theorem. Hopefully an expert like @DidierPiau can shed some light.2011-10-11

1 Answers 1

4

There is the answer, and then there is getting to the answer. I'll give a proof, and then I'll try to give some of my thought process.

Yes, $S \to 0$. Let $A(k,n) = \binom{n}{k} \left( \frac{k}{n} \right)^{2k} \left( \frac{n-k}{n} \right)^{2(n-k)}.$ Then $\frac{A(k,n)}{A(k-1,n)} = \frac{n-k+1}{k} \frac{k^{2k}}{(k-1)^{2k-2}} \frac{(n-k)^{2(n-k)}}{(n-k+1)^{2n-2k+2}}$ $=\frac{k^{2k-1}}{(k-1)^{2k-2}} \frac{(n-k)^{2n-2k}}{(n-k+1)^{2n-2k+1}} = \frac{k}{n-k} \frac{(1+1/(k-1))^{2k-2}}{(1+1/(n-k))^{2n-2k}}$ $\approx \frac{k}{n-k} \frac{e^2}{e^2} = \frac{k}{n-k} < 1$

Leaving it to you to make the bounds rigorous, this shows that $A(k,n)$ is a descreasing function of $k$.

Now, $A(2,n) = \binom{n}{2} 16/n^4 (1-2/n)^{2n-4} \leq (n^2/2) (16/n^4) = 8/n^2$. So the entire sum is $\leq A(1,n) + (n/2 -1) A(2,n) \leq n \cdot n^{-2} (1-1/n)^{2n-2} + (n/2) (8/n^2) \leq n^{-1} + 4 n^{-1}$ and this goes to zero.


So, how did I think about this? I took logs of everything. $\log \binom{n}{k} \approx k \log (n/k) + (n-k) \log (n/(n-k))$. I knew this but, if I hadn't, it follows from Stirling's approximation. So $\log A(k,n) \approx - k \log (n/k) - (n-k) \log (n/(n-k))$. So, when $k$ was of the same scale as $n$ (say k > 0.01 n), the summand $A(k,n)$ would be exponentially small. That suggested what I should do was look very carefully at the first few values of $k$, and everything else would drop out.

For $k$ a fixed small integer, I had $A(k,n) \approx (n^k/k!) k^{2k}/n^{2k} = n^{-k} (\mbox{constant})$. So any individual small $k$ term would be negligible as $n \to \infty$.

So then I had find some argument to close the gap between fixed $k$ and $k=0.01 n$. At this point, I'm not sure there is any big lesson to give, except that taking ratios of consecutive terms is often a good idea. The key point is that I already knew, from my earlier nonrigorous computations, that I expected a rapid drop off near $k=0$.