$\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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Brendan McKay Jan 18 at 10:44
  • $\begingroup$ $\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$. $\endgroup$ – VS. Jan 18 at 10:57
  • 2
    $\begingroup$ The normal approximation of the binomials will give you accurate values. $\endgroup$ – Brendan McKay Jan 18 at 11:12
  • $\begingroup$ can you explain the n-log_2f(n) and what f(n) should i expect? $\endgroup$ – VS. Jan 18 at 11:15

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|<u}P(B_n=k,C_n=n-k) =\sum_{k=0}^nP(B_n=k,C_n=n-k)-R_n=P(B_{2n}=n)-R_n, $$ 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<n-\log_2\sqrt{\mu n\ln n}$ does not hold for any real $\mu\ge1$ if $n$ is large enough.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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