A Gaussian Lower Bound for a Binomial Right Tail We show that for all integers $k \ge 1$ and all $p \in (0, \tfrac{1}{2})$ , if
$$n := 2k,\qquad \sigma^2 := p(1-p),\qquad z := \frac{(1/2 - p)\sqrt{2k}}{\sigma},$$
then
$$1 - \Phi(z) + \frac{1}{2} \binom{2k}{k},\sigma^{2k} ;\le; \mathbb{P}\bigl(\mathrm{Bin}(2k,p)\ge k\bigr),$$
where $\Phi$ is the standard normal CDF.
Equivalently: the Gaussian right tail $1-\Phi(z)$ plus the midpoint–correction term $\tfrac{1}{2} \binom{2k}{k}\sigma^{2k}$ is a lower bound for the binomial right tail.
Throughout, fix $k\in\mathbb{N}$ and set
$$n := 2k,\qquad s := p(1-p),\qquad \sigma := \sqrt{s},\qquad z := \frac{(1/2 - p)\sqrt{2k}}{\sigma}.$$
Let $\Phi$ and $\phi$ denote the standard normal CDF and PDF, respectively.
Define
$$A := \frac{1}{2} \binom{2k}{k}k, \qquad B := \frac{\sqrt{k}}{4\sqrt{\pi}}.$$
We introduce
$$I(p) := \binom{n}{k},k \int_0^p t^{k-1}(1-t)^{n-k},dt,$$
$$G(p) := 1 - \Phi\bigl(z(p)\bigr) + \frac{1}{2} \binom{n}{k},\sigma(p)^n = 1 - \Phi\bigl(z(p)\bigr) + \frac{1}{2} \binom{n}{k},s(p)^k.$$
Finally, define the "gap" function
$$\mathrm{gap}(p) := I(p) - G(p).$$
Our goal is to show $\mathrm{gap}(p) \ge 0$ for all $p\in(0,1/2)$ .
1. Integral representation of the binomial tail Let
$$T(p) := \mathbb{P}\bigl(\mathrm{Bin}(n,p)\ge k\bigr) = \sum_{i=k}^n \binom{n}{i} p^i(1-p)^{n-i}.$$
1.1. $I(p)$ is a regularized incomplete beta Recall the Beta function
$$B(a,b) = \int_0^1 t^{a-1}(1-t)^{b-1},dt = \frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)},$$
and its incomplete version
$$B(p; a,b) = \int_0^p t^{a-1}(1-t)^{b-1},dt.$$
The regularized incomplete Beta is
$$I_p(a,b) = \frac{B(p; a,b)}{B(a,b)}.$$
A standard identity for the binomial CDF (see e.g. "binomial CDF and incomplete beta") is
$$\mathbb{P}\bigl(\mathrm{Bin}(n,p)\ge k\bigr) = I_p\bigl(k,n-k+1\bigr).$$
On the other hand,
$$B\bigl(k,n-k+1\bigr) = \frac{\Gamma(k)\Gamma(n-k+1)}{\Gamma(n+1)} = \frac{(k-1)!(n-k)!}{n!},$$
so
$$\frac{1}{B(k,n-k+1)} = \frac{n!}{(k-1)!(n-k)!} = \binom{n}{k}k.$$
Thus
$$I_p(k,n-k+1) = \binom{n}{k}k \int_0^p t^{k-1}(1-t)^{n-k},dt = I(p).$$
So
$$I(p) = \mathbb{P}\bigl(\mathrm{Bin}(n,p)\ge k\bigr) = T(p).$$
1.2. Derivative form (telescoping) For completeness, differentiate $I$ and $T$ :
By the Fundamental Theorem of Calculus,
$$I'(p) = \binom{n}{k}k,p^{k-1}(1-p)^{n-k}.$$
Differentiate the finite sum defining $T(p)$ termwise:
$$\frac{d}{dp}\bigl[\binom{n}{i}p^i(1-p)^{n-i}\bigr] = \binom{n}{i}\Bigl[i p^{i-1}(1-p)^{n-i} - (n-i)p^i(1-p)^{n-i-1}\Bigr].$$
Using
$$\binom{n}{i}i = n\binom{n-1}{i-1},\qquad \binom{n}{i}(n-i) = n\binom{n-1}{i},$$
the sum telescopes, and one gets exactly
$$T'(p) = \binom{n}{k}k,p^{k-1}(1-p)^{n-k} = I'(p).$$
Since also $T(0)=0=I(0)$ , we have
$$I(p) \equiv T(p) = \mathbb{P}(\mathrm{Bin}(n,p)\ge k).$$
This will be used at the very end.
2. Endpoints and exact cancellation at $p=\tfrac{1}{2}$
We view $\mathrm{gap}(p)$ on $(0,1/2)$ , but we will extend it continuously to the closed interval $[0,1/2]$ .
$I(0) = 0$ by definition.
$s(0) = 0$ , so $\sigma(0)^n = 0$ .
As $p\to 0^+$ , $\sigma\to 0$ and $1/2 - p \to 1/2$ , so
$$z(p) = \frac{(1/2-p)\sqrt{2k}}{\sigma} \to +\infty,$$
hence $1-\Phi\bigl(z(p)\bigr) \to 0$ .
Thus
$$\lim_{p\to0^+} G(p) = 0,$$
and we define $G(0):=0$ , so that
$$\mathrm{gap}(0) = I(0) - G(0) = 0.$$
2.2. At $p = \tfrac{1}{2}$
Here
$$s = p(1-p) = \frac{1}{4},\quad \sigma^n = (1/4)^k,\quad z = 0,\quad 1-\Phi(z) = \frac{1}{2}.$$
For $X\sim \mathrm{Bin}(2k,1/2)$ , symmetry gives
$$\mathbb{P}(X \ge k) = \frac{1}{2} + \frac{1}{2}\mathbb{P}(X = k) = \frac{1}{2} + \frac{1}{2} \binom{2k}{k} 2^{-2k}.$$
But $2^{-2k} = (1/4)^k = \sigma^n$ , so
$$I\bigl(\tfrac{1}{2}\bigr) = \mathbb{P}(\mathrm{Bin}(2k,1/2)\ge k) = \frac{1}{2} + \frac{1}{2}\binom{2k}{k}\sigma^n.$$
By definition,
$$G\bigl(\tfrac{1}{2}\bigr) = 1-\Phi(0) + \frac{1}{2}\binom{2k}{k}\sigma^n = \frac{1}{2} + \frac{1}{2}\binom{2k}{k}\sigma^n.$$
Hence
$$\mathrm{gap}\bigl(\tfrac{1}{2}\bigr) = I\bigl(\tfrac{1}{2}\bigr)-G\bigl(\tfrac{1}{2}\bigr) = 0.$$
So we have
$$\mathrm{gap}(0) = \mathrm{gap}\bigl(\tfrac{1}{2}\bigr) = 0.$$
3. Derivative of the gap and reduction to a scalar inequality We compute $\mathrm{gap}'(p)$ on $(0,1/2)$ .
3.1. Derivatives of $I$ and the midpoint term As above,
$$I'(p) = \binom{n}{k}k,p^{k-1}(1-p)^{n-k}.$$
With $n=2k$ , we have
$$I'(p) = \binom{2k}{k}k,p^{k-1}(1-p)^k.$$
Writing $s=p(1-p)$ , note that
$$p^{k-1}(1-p)^k = [p(1-p)]^{k-1}(1-p) = s^{k-1}(1-p),$$
so
$$I'(p) = \binom{2k}{k}k,s^{k-1}(1-p).$$
The midpoint term is
$$M(p) := \frac{1}{2}\binom{n}{k}s^k = \frac{1}{2}\binom{2k}{k}s^k,$$
so
$$M'(p) = \frac{1}{2}\binom{2k}{k}k,s^{k-1}s' = \frac{1}{2}\binom{2k}{k}k,s^{k-1}(1-2p),$$
since $s'(p) = 1-2p$ .
3.2. Derivative of the Gaussian tail term Recall
$$z(p) = \frac{(1/2-p)\sqrt{2k}}{\sigma(p)},\qquad \sigma^2(p) = s(p).$$
Differentiating,
$$z'(p) = -\frac{\sqrt{2k}}{4,s(p)^{3/2}}.$$
(You can obtain this by a short, direct computation, using $(p-\tfrac{1}{2})^2 + s = \tfrac{1}{4}$ .)
Since $\Phi'(z) = \phi(z) = \frac{1}{\sqrt{2\pi}}e^{-z^2/2}$ , we get
$$\frac{d}{dp}\bigl[1-\Phi(z(p))\bigr] = -\phi(z(p)),z'(p) = \frac{\sqrt{2k}}{4\sqrt{2\pi}},s^{-3/2} e^{-z^2/2} = \frac{\sqrt{k}}{4\sqrt{\pi}},s^{-3/2} e^{-z^2/2}.$$
Thus
$$\frac{d}{dp}\bigl[1-\Phi(z(p))\bigr] = B,s^{-3/2}e^{-z^2/2}.$$
Recall $G(p) = 1-\Phi(z(p)) + M(p)$ . Therefore
$$G'(p) = B,s^{-3/2}e^{-z^2/2} + \frac{1}{2}\binom{2k}{k}k,s^{k-1}(1-2p).$$
Hence
$$\mathrm{gap}'(p) = I'(p) - G'(p) = I'(p) - M'(p) - \frac{d}{dp}[1-\Phi(z(p))].$$
From the formulas above,
$$I'(p) - M'(p) = \binom{2k}{k}k,s^{k-1}(1-p) - \frac{1}{2}\binom{2k}{k}k,s^{k-1}(1-2p).$$
Factor out $\binom{2k}{k}k,s^{k-1}$ :
$$I'(p) - M'(p) = \binom{2k}{k}k,s^{k-1}\left[ (1-p) - \frac{1}{2}(1-2p)\right].$$
The bracket simplifies to
$$(1-p) - \tfrac{1}{2}(1-2p) = 1-p - \tfrac{1}{2} + p = \tfrac{1}{2}.$$
So
$$I'(p) - M'(p) = \frac{1}{2}\binom{2k}{k}k,s^{k-1} = A,s^{k-1}.$$
Therefore
$$\boxed{\mathrm{gap}'(p) = A,s^{k-1} - B,s^{-3/2}e^{-z(p)^2/2}}.$$
In particular, all quantities involved are positive on $(0,1/2)$ .
3.4. Logarithmic reduction We now rewrite the sign of $\mathrm{gap}'$ in more convenient form.
Multiplying by the positive factor $s^{3/2}$ ,
$$\mathrm{gap}'(p) \ge 0 \iff A s^{k+1/2} \ge B e^{-z^2/2}.$$
Taking logs (monotone operation),
$$\mathrm{gap}'(p) \ge 0 \iff \log A + (k+\tfrac{1}{2})\log s + \frac{z^2}{2} \ge \log B.$$
Define
$$\psi(p) := \frac{z(p)^2}{2} + \left(k+\tfrac{1}{2}\right)\log s(p),\qquad C := \log\frac{B}{A}.$$
Then
$$\mathrm{gap}'(p)\ge 0 \iff \psi(p) \ge C,\qquad \mathrm{gap}'(p)\le 0 \iff \psi(p) \le C.$$
So the sign of $\mathrm{gap}'$ is completely controlled by $\psi(p)$ relative to the constant level $C$ .
4. Unimodality of $\psi$ and existence of a unique crossing We compute $\psi'(p)$ . A straightforward (but routine) differentiation gives
$$\psi'(p) = \frac{1-2p}{p(1-p)} \left[k + \tfrac{1}{2} - \frac{k}{4p(1-p)}\right].$$
Consider the two factors:
On $(0,1/2)$ , the prefactor
$$\frac{1-2p}{p(1-p)} > 0.$$
The bracket
$$f(p) := k + \tfrac{1}{2} - \frac{k}{4p(1-p)}$$
is strictly increasing in $p$ on $(0,1/2)$ , because $p\mapsto 1/(p(1-p))$ is strictly decreasing there.
Evaluate $f$ at two points:
At $p = \tfrac{1}{8}$ , $4p(1-p) = \tfrac{7}{16}$ , so
$$f(1/8) = k + \tfrac{1}{2} - \frac{16k}{7} = \frac{7 - 18k}{14} < 0$$
for all integers $k\ge 1$ .
At $p = \tfrac{1}{2}$ , $4p(1-p)=1$ , so
$$f(1/2) = k + \tfrac{1}{2} - k = \tfrac{1}{2} > 0.$$
Since $f$ is strictly increasing, there is a unique $p_0\in(1/8,1/2)$ with $f(p_0)=0$ .
Because the prefactor is positive, we conclude:
$\psi'(p) < 0$ for $p\in(0,p_0)$ (so $\psi$ is strictly decreasing there),
$\psi'(p) > 0$ for $p\in(p_0,1/2)$ (so $\psi$ is strictly increasing there).
Thus $\psi$ has a unique global minimum at $p_0$ and is "unimodal" (decrease–then–increase).
4.2. End behavior and comparison with $C$
As $p \to 0^+$ :
$s(p) = p(1-p) \sim p$ , so $\log s(p) \sim \log p$ .
$(1/2-p)\to 1/2$ , and $s(p)\to 0$ , so
$$z(p)^2 = \frac{(1/2-p)^2,2k}{s(p)} \sim \frac{k/2}{p},$$
hence
$$\frac{z(p)^2}{2} \sim \frac{k}{4p} \to +\infty.$$
The $1/p$ divergence dominates the logarithmic term, so
$$\psi(p) \to +\infty \quad \text{as } p\to 0^+.$$
At $p = 1/2$ , we have $z=0$ and $s=\tfrac{1}{4}$ , so
$$\psi\bigl(1/2\bigr) = 0 + \left(k+\tfrac{1}{2}\right)\log\frac{1}{4} = -\left(k+\tfrac{1}{2}\right)\log 4.$$
Now compute $C$ . Recall
$$A = \frac{1}{2}\binom{2k}{k}k,\qquad B = \frac{\sqrt{k}}{4\sqrt{\pi}},$$
so
$$\frac{B}{A} = \frac{\sqrt{k}}{4\sqrt{\pi}} \cdot \frac{2}{\binom{2k}{k}k} = \frac{1}{2\sqrt{\pi},\binom{2k}{k},\sqrt{k}}.$$
Using the classical upper bound
$$\binom{2k}{k} \le \frac{4^k}{\sqrt{\pi k}}$$
(Wallis' inequality), we obtain
$$\frac{B}{A} \ge \frac{1}{2\sqrt{\pi} \cdot \frac{4^k}{\sqrt{\pi k}} \cdot \sqrt{k}} = \frac{1}{2\cdot 4^k}.$$
Taking logs,
$$C = \log\frac{B}{A} \ge \log\frac{1}{2\cdot 4^k} = -\log(2) - k\log(4) = -\left(k+\tfrac{1}{2}\right)\log 4 = \psi\bigl(1/2\bigr).$$
So we have
$$\psi(p)\to+\infty \text{ as } p\to0^+,\qquad \psi\bigl(1/2\bigr) \le C,$$
and $\psi$ is strictly decreasing then strictly increasing.
4.3. Unique crossing with level $C$
Consider $f(p) := \psi(p) - C$ , which is continuous and unimodal (decrease then increase).
$\lim_{p\to 0^+} f(p) = +\infty > 0$ .
$f(1/2) = \psi(1/2) - C \le 0$ .
By continuity, there exists at least one $c\in(0,1/2)$ with $f(c)=0$ , i.e. $\psi(c)=C$ .
Because $\psi$ is strictly decreasing on $(0,p_0)$ and strictly increasing on $(p_0,1/2)$ , it can cross a horizontal level at most twice; but the inequality $\psi(1/2)\le C$ together with the fact that $\psi$ is increasing on $[p_0,1/2]$ forces $\psi(p)\le C$ on $[p_0,1/2]$ . Hence there is exactly one crossing $c\in(0,p_0]$ , and we have the sign pattern
$$\psi(p)\ge C \text{ on } (0,c],\qquad \psi(p)\le C \text{ on } [c,1/2).$$
By the equivalence from §3.4, this translates to
$$\mathrm{gap}'(p)\ge 0 \text{ on } (0,c],\qquad \mathrm{gap}'(p)\le 0 \text{ on } [c,1/2).$$
5. Sign pattern of $\mathrm{gap}'$ and conclusion We have:
$\mathrm{gap}(0) = \mathrm{gap}(1/2) = 0$ ,
$\mathrm{gap}'(p)\ge 0$ on $(0,c]$ ,
$\mathrm{gap}'(p)\le 0$ on $[c,1/2)$ .
Thus:
On $[0,c]$ , $\mathrm{gap}$ is nondecreasing and starts at $0$ , so
$$\mathrm{gap}(p) \ge \mathrm{gap}(0) = 0,\quad p\in[0,c].$$
On $[c,1/2]$ , $\mathrm{gap}$ is nonincreasing and ends at $0$ , so
$$\mathrm{gap}(p) \ge \mathrm{gap}(1/2) = 0,\quad p\in[c,1/2].$$
Therefore
$$\mathrm{gap}(p) \ge 0 \quad \text{for all } p\in[0,1/2].$$
Recalling that $I(p) = \mathbb{P}(\mathrm{Bin}(2k,p)\ge k)$ and
$$G(p) = 1 - \Phi(z(p)) + \frac{1}{2} \binom{2k}{k},\sigma(p)^{2k},$$
this gives
$$1 - \Phi\bigl(z(p)\bigr) + \frac{1}{2} \binom{2k}{k},\sigma(p)^{2k} ;\le; \mathbb{P}\bigl(\mathrm{Bin}(2k,p)\ge k\bigr)$$
for all $p\in(0,1/2)$ .
This proves the desired inequality.
