# Sum of squares of middle binomial sums or 'Truncated mean' of binomial coefficients under binomial distribution

$$\mu=1+\epsilon$$ where $$\epsilon>0$$ holds.

1.Is there a good bound for $$T=\frac{\sum_{i=-\sqrt{\mu n\ln n}}^{\sqrt{\mu n\ln n}}\binom{n}{\frac n2 +i}^2}{2^n}?$$

This quantity can be interpreted as $$\sum_{i=-\sqrt{\mu n\ln n}}^{\sqrt{\mu n\ln n}}\binom{n}{\frac n2 +i}\mathbb P(\frac n2+i)$$ where $$\mathbb P(\frac n2+i)$$ is under bionmial distribution and thus has probability $$\frac{\binom{n}{\frac n2 +i}}{2^n}$$ which is 'trucated expected value of $$\binom{n}{\frac n2 +i}$$'.

Computing few values suggests $$\log_2T< n-\log_2\sqrt{\mu n\ln n}$$ at $$\mu\rightarrow1^+$$.

For example at $$n=1000$$ to $$50000$$ gives such margin.

1. How large can $$\mu$$ be for this $$\log_2T< n-\log_2\sqrt{\mu n\ln n}$$ bound to hold up?

Naively I can get $$<\frac{2^n}{\sqrt{n\pi/2}}(1-o(1))$$ by using $$2^nT<\binom{n}{\frac n2}\sum_{i=-\sqrt{\mu n\ln n}}^{\sqrt{\mu n\ln n}}\binom{n}{\frac n2 +i}.$$

I also know we can prove $$\binom{n}{\frac n2 +i}\asymp\frac{2^{nH(\frac12+\frac in)}}{\sqrt{n\pi/2}}$$ approximation.

• I don't know if $\mu$ is something special or just a parameter, but it is odd that increasing $\mu$ makes your sums larger and your conjectured answers smaller. – Brendan McKay Jan 18 at 10:44
• $\mu=1+\epsilon$ at $\epsilon>0$. That is correct. Perhaps then the relation is flawed. On the $\log_2$ scale I see $\ll n-\log_2 f(n)$ where $f(n)$ seems to be $\Omega(\sqrt{\mu n\ln n})$ when $\mu=1.001$. – VS. Jan 18 at 10:57
• The normal approximation of the binomials will give you accurate values. – Brendan McKay Jan 18 at 11:12
• can you explain the n-log_2f(n) and what f(n) should i expect? – VS. Jan 18 at 11:15

## 1 Answer

Your main conjecture is not quite correct.

Indeed, for each natural $$j$$, let $$B_j$$ be a random variable (r.v.) with the binomial distribution with parameters $$j$$ and $$1/2$$, and let $$C_j$$ be an independent copy of $$B_j$$. Let also $$u:=\sqrt{\mu n\ln n}$$. Then for all even natural $$n$$ $$T/2^n=U_n:=\sum_{k\colon\,|k-n/2| where $$R_n:=\sum_{k\colon\, n/2\ge|k-n/2|\ge u}P(B_n=k,C_n=n-k)\le P(B_n\ge n/2+u)^2 \le e^{-4u^2/n}=1/n^{4\mu^2},$$ where, in turn, the latter inequality is an instance of an exponential Hoeffding inequality. On the other hand, by Stirling's formula, $$P(B_{2n}=n)\sim1/\sqrt{\pi n}$$ (the asymptotics everywhere here are as $$n\to\infty$$). So, $$T_n\sim2^n/\sqrt{\pi n}$$ and hence $$\log_2T=n-\log_2\sqrt{(1+o(1))\pi n}.$$

So, the inequality $$\log_2T does not hold for any real $$\mu\ge1$$ if $$n$$ is large enough.