0

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?

VS.
  • 1,816
  • On a bit of a tangent, but have you tried to use Wilf Zeilberger to generate any equivalent expressions for your $S(k,2n)$? – Zubin Mukerjee Dec 03 '19 at 07:20
  • This is the first time I am hearing Wilf Zeilberger. Perhaps you can post full answer? – VS. Dec 03 '19 at 08:16
  • Bounds from https://mathoverflow.net/q/55585/7076 may be helpful here. – Max Alekseyev Dec 03 '19 at 11:01
  • 2
    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. – Brendan McKay Dec 03 '19 at 12:37
  • So it is fair to say at $\gamma>\frac12$ we have $2n\ln2 -o(1)$? – VS. Dec 03 '19 at 12:43
  • "At every i" should probably be "for every k". – Wolfgang Dec 03 '19 at 13:19

2 Answers2

1

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.

Marcus M
  • 900
  • 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$? – VS. Jan 02 '20 at 00:15
  • Can you give me a reference on the random walk relation? – VS. Jan 10 '20 at 13:20
1

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.

skbmoore
  • 884