0
$\begingroup$

Define $S(k,2n)=\sum_{i=-k}^k\binom{2n}{n+i}$ at every $k\in\{0,\dots,n\}$.

We know $$\ln(S(\gamma\mbox{ } n^\gamma,2n))\asymp(2n\ln2-\frac12\ln\pi-\frac12\ln n)$$ at $\gamma\rightarrow0$ and $$\ln(S(\gamma\mbox{ } n^\gamma,2n))=2n\ln 2$$ at $\gamma\rightarrow1$.

Is there a good approximating expression that interpolates for $$\ln(S(\gamma\mbox{ } n^\gamma,2n))$$ at general $\gamma\in(0,1)$ between $\gamma=0$ and $\gamma=1$ here in the sense that gives information on at what $\gamma$ we may expect $2n\ln2 - f(n)$ for a given $f(n)<\frac12\ln\pi+\frac12\ln n$?

Denote $\gamma n^{\gamma}=m^{\beta}$ and $2n=m^{\alpha}$. What is the right description when $\beta<\frac\alpha2$ and $\frac\alpha2 - \frac1{c\log m}<\beta$ holds at a fixed $c>0$? Does $$m^\alpha\ln2 - (\frac\alpha2-\beta)\ln m -\frac12\ln\frac\pi2$$ seem an accurate estimate?

$\endgroup$
6
  • $\begingroup$ On a bit of a tangent, but have you tried to use Wilf Zeilberger to generate any equivalent expressions for your $S(k,2n)$? $\endgroup$ – Zubin Mukerjee Dec 3 '19 at 7:20
  • $\begingroup$ This is the first time I am hearing Wilf Zeilberger. Perhaps you can post full answer? $\endgroup$ – VS. Dec 3 '19 at 8:16
  • $\begingroup$ Bounds from mathoverflow.net/q/55585/7076 may be helpful here. $\endgroup$ – Max Alekseyev Dec 3 '19 at 11:01
  • 2
    $\begingroup$ I don't get the "$1-\gamma$" term as it subtracts at most one term from each end of the sum. Leaving that aside, for $\gamma\gt \frac12$ you have $2n\ln 2$ and for smaller $\gamma$ you have the normal approximation of the binomial distribution. $\endgroup$ – Brendan McKay Dec 3 '19 at 12:37
  • $\begingroup$ So it is fair to say at $\gamma>\frac12$ we have $2n\ln2 -o(1)$? $\endgroup$ – VS. Dec 3 '19 at 12:43
1
$\begingroup$

I think the best intuition is to translate it to a question about random walk. Let $S_{n}$ be a simple random walk with $n$ steps. Then $$S(k,2n) = 4^{n} \mathbb{P}(|S(2n)| \leq k).$$

Thus, for $\gamma > 1/2$, we have $S(\gamma n^\gamma,2n) \sim 4^n$ and for $\gamma < 1/2$ we have $$S(\gamma n^{\gamma},2n) \sim \frac{\gamma n^{\gamma} 4^{n}}{\sqrt{ \pi n}}.$$

At $\gamma = 1/2$, the central limit theorem takes over and so we calculate $$S(n^{1/2}/2,2n) = 4^{n} \mathbb{P}(|S(2n)| \leq n^{1/2}/2) = 4^n \mathbb{P}(\frac{|S(2n)|}{\sqrt{2n}} \leq 2^{-3/2}) \sim 4^n \mathbb{P}(|Z| \leq 2^{-3/2})$$

where $Z$ is a standard normal variable.

$\endgroup$
2
  • $\begingroup$ Is it possible to make precise the constants in $S(\gamma n^\gamma,2n)\sim4^n$ when $\gamma>\frac12$ say when $\gamma n^\gamma=n^{\frac12+\frac1d\frac{\log_2 c}{\log_2n}}$ at some fixed $c,d>1$ and $S(\gamma n^\gamma,2n)\sim\frac{\gamma n^\gamma 4^n}{\sqrt{\pi n}}$ when $\gamma<\frac12$ say when $\gamma n^\gamma=n^{\frac12-\frac1d\frac{\log_2 c}{\log_2n}}$ at some fixed $c,d>1$? $\endgroup$ – VS. Jan 2 '20 at 0:15
  • $\begingroup$ Can you give me a reference on the random walk relation? $\endgroup$ – VS. Jan 10 '20 at 13:20
1
$\begingroup$

An approximation that works well is $$ \frac{S(k,2n)}{\binom{2n}{n}} \sim \sqrt{\pi \, n}\, \text{erf }(k/\sqrt{n})+\exp{(-k^2/n)}.$$ For instance, letting $n=100$ and letting $k$ run from 0 to $n,$ the maximum error is about 0.12%. For $n=10^3,$ max err is 0.014% and for $n=10^4,$ max err is 0.0016%.

I derived it from the gaussian approximation of the central binomial, and Euler-McLaurin, that is:

$$ (*) \quad \quad \frac{\binom{2n}{n+m}}{\binom{2n}{n}} \sim \exp{(-m^2/n)} $$ $$ \sum_{m=-k}^{k}\frac{\binom{2n}{n+m}}{\binom{2n}{n}} \sim \int_{-k}^{k}\exp{(-m^2/n)} \,dm + \exp{(-k^2/n)} + ... $$ where the (...) indicate the terms in sum involving the Bernoulli numbers and derivatives of the gaussian. This expression is probably better than it deserves, as I've only included the first asymptotic term in (*) and neglected the (...) terms. This analysis is not rigorous, but might give you an avenue to explore.

$\endgroup$
1
  • $\begingroup$ what is the error term in the expression? $\endgroup$ – VS. Jan 3 '20 at 23:36

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.