Show $\sum_{k: \left| k - \frac{n}{2} \right| \le \frac{x \cdot \sqrt{n}}{2}} \binom{n}{k} \sim 2^n \int_{-x}^{x} \frac{e^{-u/2}}{\sqrt{2 \pi}} du$

Question

Using the central limit theorem, I want to prove that

$$ \sum_{\substack{k: \\\left| k - \frac{n}{2} \right| \le \frac{x \cdot \sqrt{n}}{2}}} \binom{n}{k} \sim 2^n \int_{-x}^{x} \frac{e^{-u^2/2}}{\sqrt{2 \pi}} du \qquad (n \to \infty). $$

This is one formulation of the CLT I have at hand: for all $x \ge 0$ it holds that $$ \mathbb{P}\left( \left|\sqrt{\frac{n}{\sigma^2}} \left( \frac{S_n}{n} - m \right) \right| \le x \right) \xrightarrow{n \to \infty} \frac{1}{\sqrt{2 \pi}} \int_{-x}^{x} e^{-\frac{y^2}{2}} dy, $$ where $(X_k)_{k \in \mathbb{N}}$ are i.i.d. random variables with $S_n := \sum_{k = 1}^{n} X_k$, $\mathbb{E}[X_1] =: m$, $\text{Var}[X_1] = \sigma^2 \in (0, \infty)$,

My ideas Algebraic manipulation yields $$ \mathbb{P}\left( \left|\sqrt{\frac{n}{\sigma^2}} \left( \frac{S_n}{n} - m \right) \right| \le x \right) = \mathbb{P}(| S_n - n m | \le \sqrt{n} \cdot x \cdot \sigma). $$ Therefore I am searching a sequence of (discrete) random variables with $m = \sigma^2 = \frac{1}{2}$ and $S_n = k$.

Since their expected value and variance are the same I thought of the poisson distribution but I wouldn't get any binomial coefficients when I use its cummulative distribution function so I guess it is the binomial distribution but I don't know for which parameters.

Answer 1

Everything boils down to find $S_n, m, \sigma$ so that:

$$P\Big( \Big\vert \frac{\sqrt{n}}{\sigma} \Big( \frac{S_n}{n} - m \Big) \Big\vert \leq x \Big) = \sum_{k: \Big\vert \frac{2k}{\sqrt n} - \sqrt n \Big\vert \leq x} \frac{1}{2^n} \binom{n}{k} $$

The LHS can be rewritten as: \begin{align*} &P\Big( \Big\vert \frac{\sqrt{n}}{\sigma} \Big( \frac{S_n}{n} - m \Big) \Big\vert \leq x \Big) = \sum_{u : \vert u \vert \leq x} P \Big( \frac{\sqrt{n}}{\sigma} \Big( \frac{S_n}{n} - m \Big) = u \Big) \\ &= \sum_{k : \Big\vert \frac{2k}{\sqrt n} - \sqrt n \Big\vert \leq x} P \Big( \frac{\sqrt{n}}{\sigma} \Big( \frac{S_n}{n} - m \Big) = \frac{2k}{\sqrt n} - \sqrt n \Big) (\text{by changing variable}) \\ &= \sum_{k : \Big\vert \frac{2k}{\sqrt n} - \sqrt n \Big\vert \leq x} P \Big( \frac{\sqrt{n}}{\sigma} \Big( \frac{S_n}{n} - m \Big) = \frac{k - n/2}{\sqrt n / 2} \Big) \\ &= \sum_{k : \Big\vert \frac{2k}{\sqrt n} - \sqrt n \Big\vert \leq x} P \Big(\frac{S_n - mn}{\sigma \sqrt n} = \frac{k - n/2}{\sqrt n / 2} \Big) \end{align*}

The RHS can be rewritten as: \begin{align*} \sum_{k: \Big\vert \frac{2k}{\sqrt n} - \sqrt n \Big\vert \leq x} \frac{1}{2^n} \binom{n}{k} = \sum_{k: \Big\vert \frac{2k}{\sqrt n} - \sqrt n \Big\vert \leq x} P(Z = k) = \sum_{k: \Big\vert \frac{2k}{\sqrt n} - \sqrt n \Big\vert \leq x} P(\frac{Z-n/2}{\sqrt n / 2} = \frac{k - n/2}{\sqrt n / 2}) \end{align*} where $Z \sim Binomial(n, 1/2)$. By identifying these relations, we have $m = \sigma = 1/2$. So naturally we will choose $X_i \sim Ber(1/2)$ and $S_n = \sum X_i \sim Binomial(n, 1/2)$.

Answer 2

The question appears to need an $u^2,$ not $u$ in the argument of the exponential.

For convenience, I'll work with $2n,$ It is easy to show with Stirling asymptotics that for 'small' $k$ we have

$$ \binom{2n}{n+k} = \binom{2n}{n} \exp{(-k^2/n)}\Big(1 + \frac{k^2}{2n^2} + ...\Big) $$ Usually 'small k' is taken to mean $k=\cal{o}(\sqrt{n})$ so the last term can be dropped, which I'll do in the following. Then

$$ S:=\sum_{|k-n|<x\sqrt{n/2}} \binom{2n}{k} = \sum_{k=-x\sqrt{n/2}}^{x\sqrt{n/2}} \binom{2n}{n+k} \sim \frac{n}{n} \binom{2n}{n}\sum_{k=-x\sqrt{n/2}}^{x\sqrt{n/2}} \exp{(-n\,(k/n)^2)}.$$ Use the Riemann sum relation $$\frac{1}{n} \sum_{k=a}^b f(k/n) \sim \int_{a/n}^{b/n}f(u)\,du $$ and the expansion of the central binomial $$ \binom{2n}{n} \sim 2^{2n}/\sqrt{\pi n}$$ to get $$S \sim n \frac{ 2^{2n}}{\sqrt{\pi n}} \int_{-x/\sqrt{2n}}^{x/\sqrt{2n}}\exp{(-n\,u^2)}\,du.$$ Scaling the integrand by $u \to u/\sqrt{2n} $ gives the answer you want,

$$ S \sim \frac{ 2^{2n}}{\sqrt{2 \pi }}\int_{-x}^{x}\exp{(-u^2/2)}\,du. $$

Keeping the discarded $(k/n)^2$ and with the u-scaling shows that within the integrand we have neglected a term of $\cal{O}(u^2/n).$ Thus $x$ must be small, say, $\cal{o}(\sqrt{n}).$