I have seen the following bound somewhere, but could not find it.
Let $n$ be an non negative integer and $X \sim Bin(n,\frac{1}{2})$. Show that there exists an abosolute constant $c > 0$, such that $Pr\big[X \leq \frac{n}{2} - \frac{1}{2}\sqrt{\frac{n}{2}}\big] \geq c$.
Note that $\mathbb{E}X = \frac{n}{2}$, so the above lemma says that $X$ can not be too close to the mean. Can someone give a reference to this result, or an outline of a proof?
Thanks
Ok, I am presenting a proof using Berry–Esseen theorem .
$X$ can be thought of as sum of unbiased Bernoulli random variables $X_i$, $X = \sum_{i=1}^n X_i$, where $P[X_i=1] = \frac{1}{2} = P[X_i=0]$.
Now define $X^\prime_i = X_i -\frac{1}{2}$. We have \begin{align*} \mathbb{E}[X_i] &= 0\\ \sigma^2 = \mathbb{E}[X_i^{\prime 2}] &= \frac{1}{4} > 0\\ \rho = \mathbb{E}[\vert X_i^\prime\vert^3] = \frac{1}{8} < \infty \end{align*} Define $Y = \frac{X}{\sigma\sqrt{n}} = \frac{2X}{\sqrt{n}}$. Then $\mathbb{E}[Y] = \sqrt{n}$.
Berry-Esseen them implies that \begin{align*} \vert F_Y(x) - \Phi(x)\vert \leq \frac{C\rho}{\sigma^3\sqrt{n}} = \frac{C}{\sqrt{n}} \end{align*} Where $C$ is an absolute constant $< 1$ and $F_Y()$ is the cdf of $Y$. Now observe that $X \leq \frac{n}{2} - \frac{1}{2}\sqrt{\frac{n}{2}}$ is same as $Y \leq \sqrt{n} - \frac{1}{\sqrt{2}}$. So
\begin{align*} F_Y(\sqrt{n} - \frac{1}{\sqrt{2}}) \geq \Phi(\sqrt{n} - \frac{1}{\sqrt{2}}) - \frac{C}{\sqrt{n}} \end{align*} Since $n\geq 1$, the second term is $C$ and $\Phi(\sqrt{n} - \frac{1}{\sqrt{2}}) \geq \Phi(1 - \frac{1}{\sqrt{2}})$, a constant and we are done.
I think this justifies the $\sqrt{n}$ term as well. Also, I this the reverse inequality can also be proven in a similar manner, i.e.